poj3436 ACM Computer Factory， 最大流，輸出路徑

poj3436 ACM Computer Factory， 最大流，輸出路徑

電腦公司生產電腦有N個機器，每個機器單位時間產量為Qi。

電腦由P個部件組成，每個機器工作時只能把有某些部件的半成品電腦(或什麼都沒有的空電腦）變成有另一些部件的半成品電腦或完整電腦(也可能移除某些部件）。求電腦公司的單位時間最大產量，以及哪些機器有協作關系，即一台機器把它的產品交給哪些機器加工。

Sample input
3 4
15 0 0 0 0 1 0
10 0 0 0 0 1 1
30 0 1 2 1 1 1
3 0 2 1 1 1 1

Sample output
25 2
1 3 15
2 3 10

輸入：電腦由3個部件組成，共有4台機器，1號機器產量15, 能給空電腦加上2號部件，2號 機器能給空電腦加上2號部件和3號部件, 3號機器能把有1個2號部件和3號部件有無均可的電腦變成成品（每種部件各有一個）

輸出：單位時間最大產量25,有兩台機器有協作關系，
1號機器單位時間內要將15個電腦給3號機器加工
2號機器單位時間內要將10個電腦給3號機器加工

數據規模很小，用EdmondsKarp就可以了。主要題目不僅要求最大流的值還要輸出有流流過的邊。

仔細想一想，這題不用拆點！

#include
#include
#include
#include
#include

using namespace std;

typedef long long LL;
const int maxn = 60;
const int inf = 0x7fffffff;

struct Edge {
    int from,to,cap,flow;
    Edge(int u,int v,int c,int f):from(u),to(v),cap(c),flow(f) {}
};
struct EdmondsKarp {
    int n,m;
    vector edges;
    vector G[maxn];
    int p[maxn];
    int a[maxn];

    void init(int n)
    {
        this->n=n;
        for(int i=0; i Q;
            Q.push(s);
            a[s]=inf;
            while(!Q.empty()) {
                int x=Q.front();
                Q.pop();
                for(int i=0; ie.flow) {
                        a[e.to]=min(a[x],e.cap-e.flow);
                        p[e.to]=G[x][i];
                        Q.push(e.to);
                        if(e.to==t)
                            break;
                    }
                }
                if(a[t])break;
            }
            if(!a[t])break;
            for(int u=t; u!=s; u=edges[p[u]].from) {
                edges[p[u]].flow+=a[t];
                edges[p[u]^1].flow-=a[t];
            }
            flow+=a[t];
        }
        return flow;
    }
};

EdmondsKarp solver;

int P, N;
int w[maxn], in[maxn][12], out[maxn][12];

int print[maxn][5], cnt;
int main()
{
    int i, j;
    bool flag;
    while(~scanf("%d%d", &P, &N)) {
        int s = 0, t = N+1;
        solver.init(N+2);
        for(int i=1; i<=N; ++i) {
            scanf("%d", &w[i]);
            flag = true;
            for(j=0; j0 && e.to != t && e.from != s)
            {
                print[cnt][0] = e.from;
                print[cnt][1] = e.to;
                print[cnt++][2] = e.flow;
            }
        }
        printf("%d\n", cnt);
        for(i=0; i