POJ_3436 ACM Computer Machine (网络流)

　　参考郭炜老师课件上的代码。思路是建立一个超级源点和一个超级汇点，先输入的串如果是0000....或02...的形式，则与源点相连，后输入的串如果为1111...则与超级汇点相连。

然后拆点，把从入机器前的状态到如机器后的状态看成一个流，流的最大量就是该机器每小时可以加工的元件数。然后用EK的优化——Dinic。思路就是在先用bfs把图中所有的结点标上按遍历的顺序标上层次，这样找到一条增广路径后就不需要退到0号结点，而是推倒所找的增广路径上跟下一个结点的容量是最小容量的那个结点。、

Code:

#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>

using namespace std;

const int M = 110;
const int inf = 0x6fffffff;

struct machine {
    int l;
    int in[11];
    int out[11];
}mach[M];

int g[M][M];
int fg[M][M];
int layer[M];
bool vis[M];
int P, N, T;

bool Equal(int *a, int *b, int P) {
    for(int i = 0; i < P; i++) {
        if(a[i] + b[i] == 1)    return false;
    }
    return true;
}

bool Layer() {
    deque<int> q;
    int i, v;
    memset(layer, -1, sizeof(layer));
    q.push_back(0);
    layer[0] = 1;
    while( !q.empty()) {
        v = q.front();
        q.pop_front();
        for(i = 0; i <= T; i++) {
            if(g[v][i] > 0 && layer[i] == -1) {
                layer[i] = layer[v] + 1;
                if(i == T)     {q.clear(); return true;}
                else    q.push_back(i);
            }
        }
    }
    return false;
}

int Dinic() {
    int i, v, sum = 0, Min, Min_s, s, e;

    deque<int> q;
    while(Layer()) {
        memset(vis, 0, sizeof(vis));
        vis[0] = true;
        q.push_back(0);
        while(!q.empty()) {
            v = q.back();
            if(v == T) {
                Min = inf;
                for(i = 1; i < q.size(); i++) {
                    s = q[i-1];
                    e = q[i];
                    if(g[s][e] > 0 && Min > g[s][e]) {
                        Min = g[s][e];
                        Min_s = s;
                    }
                }
                sum += Min;
                for(i = 1; i < q.size(); i++) {
                    s = q[i-1];
                    e = q[i];
                    if(g[s][e] > 0) {
                        g[s][e] -= Min;
                        g[e][s] += Min;
                    }
                }
                while(!q.empty() && q.back() != Min_s) {
                    vis[q.back()] = false;
                    q.pop_back();
                }
            } else {
                for(i = 0; i <= T; i++) {
                    if(g[v][i] > 0 && layer[i] == layer[v] + 1 && !vis[i]) {
                        vis[i] = true;
                        q.push_back(i);
                        break;
                    }
                }
                if(i > T)    q.pop_back();
            }
        }
    }
    return sum;
}

int main() {
    //freopen("data.in", "r", stdin);

    int i, j, k, sum, edg;
    while(~scanf("%d%d", &P, &N)) {
        memset(g, 0, sizeof(g));
        memset(mach, 0, sizeof(mach));
        for(i = 1; i <= N; i++) {
            scanf("%d", &mach[i].l);
            for(j = 0; j < P; j++)
                scanf("%d", &mach[i].in[j]);
            for(j = 0; j < P; j++)
                scanf("%d", &mach[i].out[j]);
            g[i][i+N] = mach[i].l;
        }
        T = 2 * N + 1;
        for(i = 1; i <= N; i++) {
            for(j = i+1; j <= N; j++) {
                if(Equal(mach[i].out, mach[j].in, P))
                    g[i+N][j] = inf;
                if(Equal(mach[j].out, mach[i].in, P))
                    g[j+N][i] = inf;
            }
            g[0][i] = inf;
            for(k = 0; k < P; k++) {
                if(mach[i].in[k] == 1) {
                    g[0][i] = 0; break;
                }
            }
            g[i+N][T] = inf;
            for(k = 0; k < P; k++) {
                if(mach[i].out[k] != 1) {
                    g[i+N][T] = 0; break;
                }
            }
        }
        memcpy(fg, g, sizeof(g));
        sum = Dinic();
        edg = 0;
        for(i = N+1; i < T; i++) {
            for(j = 1; j <= N; j++) {
                if(g[i][j] < fg[i][j])
                    edg++;
            }
        }
        printf("%d %d\n", sum, edg);
        for(i = N + 1; i < T; i++) {
            for(j = 1; j <= N; j++) {
                if(g[i][j] < fg[i][j])
                    printf("%d %d %d\n", i-N, j, fg[i][j] - g[i][j]);
            }
        }
    }
    return 0;
}