Brief description :

判断流网络割是否唯一。

Analyse :

最大流完事以后，从源点和汇点处分别染色。

/*
    Author: xiaodao    
    Prob: ZOJ 2587. Unique Attack        
    Date: GMT +8 Aug.19th 02:36
    Status: Accepted        
    Tags: Network-Flow
*/

#include 
#include 
#include 
using namespace std;
const int INF = 0x7fffffff, BLACK = 0, RED = 1, BLUE = 2;
const int N = 1001;
int C[N][N], D[N];
int n, m, s, t;

void bfs(){
    int Q[N], head, tail;
    memset(D, -1, sizeof(D));
    head = 0; tail = 1; Q[0] = s; D[s] = 0;

    int u, v;
    while (headn) D[u] = -1, top--;
            else {
                cur[u] = v + 1;
                stack[++top] = v;
            }
        }
        bfs();
    }
}



void init(){
    memset(C, 0, sizeof(C));
    int x, y, c;
    for (int i=1;i<=m;i++){
        scanf("%d%d%d", &x, &y, &c);
        C[x][y] += c; C[y][x] += c;
    }
}

bool unique(){
    int queue[N]; int color[N];
    int head, tail, u, v;
    memset(color, BLACK, sizeof(color));
    head = 0; tail = 1; queue[0] = s; color[s] = RED;


    while (head0){
                queue[tail++] = v;
                color[v] = RED;
            }
        }
        head++;
    }

    head = 0; tail = 1; queue[0] = t; color[t] = BLUE;
    while (head=1;u--){
            if (color[u]!=BLUE && C[u][v]>0){
                if (color[u] == RED) return false;
                queue[tail++] = u;
                color[u] = BLUE;
            }
        }
        head++;
    }

    for (int i=1;i<=n;i++)
        if (color[i] == BLACK) return false;
    return true;
}



int main(){
    while (scanf("%d%d%d%d", &n, &m, &s, &t) != EOF && n > 0){
        init(); Dinitz();
        puts(unique() ? "UNIQUE" : "AMBIGUOUS");
    }
}

Further discuss :

好了我来说点正事。。。我这几天爆写了十几个（几个啦）各种网络流的题。
。。。比如说像是这个。。昨晚就写完了。。然后一直WA一直WA。。心想。。难不成我的 Relabel 有BUG？#。 （于是几个深夜又学习了 Dinitz … Sap … 目前按照计划只差一个 HLPP 了。。）

但是我继续爆WA..

于是我发现我WA的几个网络流都有一些共同点。。。
（快说啊。。。#）

事实上。。因为我人工将源点和汇点固定成 1 && n 会有许多说不清的好处。。。（例如。。我总是可以优化。。#。#）

...
    if (s!=1){
        for (int i=1;i<=n;i++){
            if (i==1||i==s) continue;
            swap(C[1][i], C[s][i]);
            swap(C[i][1], C[i][s]);
        }
        swap(C[1][s], C[s][1]);
    }

    if (t!=n){
        for (int i=1;i<=n;i++){
            if (i==n||i==t) continue;
            swap(C[n][i], C[t][i]);
            swap(C[i][n], C[i][t]);
        }
        swap(C[n][t], C[t][n]);
    }
    s = 1; t = n;
                              ....

实际上。。我之前的方案更暴力。。就是一个循环里面嵌两个交换。。
（但是我已经发现那样是错误的了。。。但是我不能发现。。这个错在哪。）

Posted by xiaodao
Category: 日常