BZOJ 1797 AHOI 2009 Mincut 最小割 最小割

BZOJ 1797 AHOI 2009 Mincut 最小割 最小割

題目大意：給出一個網絡圖，求出這其中的可行邊和必須邊。

思路：看了策爺的博客，知道了兩個結論：

最小割的必須邊和可行邊：

求最大流，在殘余網絡中求出SCC。若：

1. 對於任意一條滿流邊，有changed[x] != changed[y]，則這個邊為可行邊。

2. 對於任意一條滿流邊，有changed[x] == changed[S] && changed[y]== changed[T]，則這個邊為必須邊。

之後就是結論題了。

CODE：

#include 
#include 
#include 
#include 
#include 
#define MAX 120010 
#define INF 0x3f3f3f3f
using namespace std;
 
int points,edges,S,T;
int head[MAX],total = 1;
int next[MAX << 1],aim[MAX << 1],from[MAX << 1],flow[MAX << 1];
 
int deep[MAX];
int dfn[MAX],changed[MAX],scc;
 
inline void Add(int x,int y,int f)
{
    next[++total] = head[x];
    aim[total] = y;
    from[total] = x;
    flow[total] = f;
    head[x] = total;
}
 
inline void Insert(int x,int y,int f)
{
    Add(x,y,f);
    Add(y,x,0);
}
 
inline bool BFS()
{
    static queue q;
    while(!q.empty())   q.pop();
    memset(deep,0,sizeof(deep));
    deep[S] = 1;
    q.push(S);
    while(!q.empty()) {
        int x = q.front(); q.pop();
        for(int i = head[x]; i; i = next[i]) 
            if(flow[i] && !deep[aim[i]]) {
                deep[aim[i]] = deep[x] + 1;
                q.push(aim[i]);
                if(aim[i] == T) return true;
            }
    }
    return false;
}
 
int Dinic(int x,int f)
{
    if(x == T)  return f;
    int temp = f;
    for(int i = head[x]; i; i = next[i])
        if(flow[i] && deep[aim[i]] == deep[x] + 1 && temp) {
            int away = Dinic(aim[i],min(temp,flow[i]));
            if(!away)   deep[aim[i]] = 0;
            flow[i] -= away;
            flow[i^1] += away;
            temp -= away;
        }
    return f - temp;
}
 
void Tarjan(int x)
{
    static int low[MAX],total;
    static int stack[MAX],top;
    static bool in_stack[MAX];
    dfn[x] = low[x] = ++total;
    stack[++top] = x;
    in_stack[x] = true;
    for(int i = head[x]; i; i = next[i])
        if(flow[i]) {
            if(!dfn[aim[i]])
                Tarjan(aim[i]),low[x] = min(low[x],low[aim[i]]);
            else if(in_stack[aim[i]])
                low[x] = min(low[x],dfn[aim[i]]);
        }
    if(low[x] == dfn[x]) {
        ++scc;
        int temp;
        do {
            temp = stack[top--];
            in_stack[temp] = false;
            changed[temp] = scc;
        }while(temp != x);
    }
}
 
int main()
{
    cin >> points >> edges >> S >> T;
    for(int x,y,z,i = 1; i <= edges; ++i) {
        scanf("%d%d%d",&x,&y,&z);
        Insert(x,y,z);
    }
    while(BFS())
        Dinic(S,INF);
    for(int i = 1; i <= points; ++i)
        if(!dfn[i]) Tarjan(i);
    for(int i = 2; i <= edges << 1; i += 2) {
        if(!flow[i]) {
            if(changed[from[i]] != changed[aim[i]])
                printf("1 ");
            else    printf("0 ");
            if(changed[S] == changed[from[i]] && changed[T] == changed[aim[i]])
                puts("1");
            else    puts("0");
        }
        else    puts("0 0");
    }
    return 0;
}