Brief description :

判断流网络的边集，在最小割中，是否有可能成为割边的？是否一定会成为割边？

Analyse :

Orz hf46中 MSK 神牛的题。。。
http://hi.baidu.com/matrush/blog/item/091adb03b4eedd0d728da54c.html

/*
    Author  : xiaodao
    Problem : AHOI 2009 Mincut 最小割
    Status  : Accepted
    Last Modify : GMT +8. Sept 14th 08:12.
    Tags : 网络流，最小割，强连通分量
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <cmath>

using namespace std;
const int INF = 0x7fffffff;
const int N = 40100, M = 123001;
struct edge{
    int v, c;
    void insert(int, int);
};
struct node{
    vector<int> adj;
    int D, scc;
};
struct network_flow{
    node V[N+1]; edge E[M+1];
    int edge_count; int max_flow;
    int n, m, s, t;
    bool C[N+1]; int F[N+1] ,time;
    int component;

    void init();
    void print();
    void add_edge(int, int, int);
    void bfs(); void dfs1(int); void dfs2(int);
    void Dinitz();
    void Kosaraju();
};
inline int _r(int x){
    return x ^ 1;
}
void edge::insert(int a, int b){
    v = a; c = b;
};
void network_flow::add_edge(int x, int y, int z){
    V[x].adj.push_back(edge_count); E[edge_count++].insert(y, z);
}


void network_flow::bfs(){
    int Q[N+1] = {s}, head = 0, tail = 1;
    for (int i=1;i<=n;i++) V[i].D = -1;
    V[s].D = 0;

    int u;
    while (head<tail){
        u = Q[head];
        for (size_t i=0;i<V[u].adj.size();i++){
            edge &arc = E[V[u].adj[i]];
            if (V[arc.v].D==-1 && arc.c>0){
                Q[tail] = arc.v; V[arc.v].D = V[u].D + 1;
                if (arc.v == t) return;
                tail++;
            }
        }
        head++;
    }
}

void network_flow::Dinitz(){
    max_flow = 0;

    bfs();
    while (V[t].D!=-1){
        int stack[n+1], cur[n+1], top = 0;
        memset(cur, 0, sizeof(cur));
        stack[0] = M;

        int u; size_t i;
        while (top!=-1){
            u = E[stack[top]].v;
            if (u == t){
                int delta = INF; int handle;
                for (int i=1;i<=top;i++){
                    edge &arc = E[stack[i]];
                    if (arc.c < delta){
                        delta = arc.c;
                        handle = i;
                    }
                }
                max_flow += delta;
                for (int i=1;i<=top;i++){
                    E[stack[i]].c -= delta;
                    E[_r(stack[i])].c += delta;
                }

                //for (int i=handle;i<=top;i++){
                  //  cur[stack[i]] = 0;
                //}  // ?

                top = handle-1;
                continue;
            }

            for (i=cur[u];i<V[u].adj.size();i++){
                edge &arc = E[V[u].adj[i]];
                if (V[arc.v].D == V[u].D + 1 && arc.c>0) break;
            }

            if (i == V[u].adj.size()){
                V[u].D = -1, top--;
            }
            else {
                cur[u] = i + 1;
                stack[++top] = V[u].adj[i];
            }
        }
        bfs();
    }
}



void network_flow::dfs1(int u){
    C[u] = true;
    for (int i=0;i<V[u].adj.size();i++){
        edge &arc = E[V[u].adj[i]];
        if (!C[arc.v] && arc.c!=0)
            dfs1(arc.v);
    }
    F[time++] = u;
}

void network_flow::dfs2(int u){
    C[u] = true; V[u].scc = component;
    for (int i=0;i<V[u].adj.size();i++){
        edge &rev_arc = E[_r(V[u].adj[i])];
        edge &arc = E[V[u].adj[i]];
        if (!C[arc.v] && rev_arc.c!=0)
            dfs2(arc.v);
    }
}


void network_flow::Kosaraju(){
    memset(C, false , sizeof(C)); time = 0;
    for (int i=1;i<=n;i++)
        if (!C[i]) dfs1(i);

    memset(C, false, sizeof(C));
    component = 0;
    for (int i=n-1;i>=0;i--)
        if (!C[F[i]]) dfs2(F[i]), component++;
}



void network_flow::init(){
    for (int i=1;i<=n;i++) V[i].adj.clear();
    edge_count = 0; E[M].v = s;

    int x, y, z;
    for (int i=0;i<m;i++){
        scanf("%d%d%d", &x, &y, &z);
        add_edge(x, y, z);
        add_edge(y, x, 0);
    }
}

void network_flow::print(){
    for (int i=0;i<m;i++)
        if (E[2*i].c !=0 || V[E[2*i+1].v].scc == V[E[2*i].v].scc) printf("0 0\n");
        else {
            if (V[E[2*i+1].v].scc != V[s].scc || V[E[2*i].v].scc != V[t].scc)  printf("1 0\n");
            else printf("1 1\n");
        }
}


network_flow G;

int main(){
    //freopen("in.txt", "r", stdin);
    while (scanf("%d%d%d%d", &G.n, &G.m, &G.s, &G.t)==4){
        G.init(); G.Dinitz(); G.Kosaraju();
        G.print();
    }
}

— UPD —
https://gist.github.com/lychees/3a09545e29380bed4a00

Posted by xiaodao
Category: BZOJ