题目链接：

题意:

每台ACM 计算机包括P 个部件。当全部这些部件都准备齐全后，计算机就能够组装了。组装好以后就能够交给竞赛队伍使用了。

计算机的生产过程是全自己主动的，通过N 台不同的机器来完毕。

每台机器从一台半成品计算机中去掉一些部件。并增加一些新的部件（去除一些部件在有的时候是必须的，由于计算机的部件不能以随意的顺序组装）。

每台机器用它的性能（每小时组装多少台计算机）、输入/输出规格来描写叙述。

输入规格描写叙述了机器在组装计算机时哪些部件必须准备好了。输入规格是由P 个整数组成。每一个整数代表一个部件。这些整数取值为0, 1 或2，当中0 表示该部件不应该已经准备好了。1表示该部件必须已经准备好了。2 表示该部件是否已经准备好了无关紧要。

输出规格描写叙述了该机器组装的结果。

输出规格也是由P 个整数组成，每一个整数取值为0 或1，当中0 代表该部件没有生产好，1 代表该部件生产好了。

机器之间用传输速度很快的流水线连接。部件在机器之间传送所需的时间与机器生产时间相比是十分小的。

给出上述关于n台机器的描写叙述,求一小时最多组成多少台计算机,并输出流水线的路径

解题思路:

题目已给出条件:  机器之间传输不须要时间,也就能够理解为流水线上每台机器的工作都是同步的，这样就能够用网络流来攻克了(单位时间问题)

解题的关键在于建图.

话不多说,给出一张例子图:

图中红色边的容量应设为无穷大(单位时间运输无限台计算机)

值得注意的是  图中两台机器的连接能够是双向的(比方能够同一时候又B1->A2 ,B2->A1 )

关于路径的输出(找从n+1~2*n)開始的正向边,有流则表示生产线经过这条路径

代码:

#include 
     
      #include 
      
       #include
       
        #define LL long long#include 
        
         const int MAXN =205;const int MAXM=440020;const int INF=0x3f3f3f3f;using namespace std;struct Edge{    int from;    int to,cap,flow,next;} edge[MAXM];int head[MAXN],tot,gap[MAXN],d[MAXN],cur[MAXN],que[MAXN],p[MAXN];void init(){    tot=0;    memset(head,-1,sizeof(head));}void addedge(int u,int v,int c,int f){    edge[tot]=(Edge)    {        u,v,c,f,head[u]    };    head[u] = tot++;    edge[tot]=(Edge)    {        v,u,c,c,head[v]    };    head[v] = tot++;}int isap(int source,int sink,int N){    memset(gap,0,sizeof(gap));    memset(d,0,sizeof(d));    memcpy(cur,head,sizeof(head));    int top = 0,x = source,flow = 0;    while(d[source] < N)    {        if(x == sink)        {            int Min = INF,inser=0;            for(int i = 0; i < top; ++i)            {                if(Min > edge[p[i]].cap - edge[p[i]].flow)                {                    Min = edge[p[i]].cap - edge[p[i]].flow;                    inser = i;                }            }            for(int i = 0; i < top; ++i)            {                edge[p[i]].flow += Min;                edge[p[i]^1].flow -= Min;            }            if(Min!=INF) flow += Min;            top = inser;            x = edge[p[top]^1].to;            continue;        }        int ok = 0;        for(int i = cur[x]; i != -1; i = edge[i].next)        {            int v = edge[i].to;            if(edge[i].cap > edge[i].flow && d[v]+1 == d[x])            {                ok = 1;                cur[x] = i;                p[top++] = i;                x = edge[i].to;                break;            }        }        if(!ok)        {            int Min = N;            for(int i = head[x]; i != -1; i = edge[i].next)            {                if(edge[i].cap > edge[i].flow && d[edge[i].to] < Min)                {                    Min = d[edge[i].to];                    cur[x] = i;                }            }            if(--gap[d[x]] == 0) break;            gap[d[x] = Min+1]++;            if(x != source) x = edge[p[--top]^1].to;        }    }    return flow;}int state[MAXN][2][10];int pp,n;int equall(int x,int y){    for(int i=0;i
         
          0){                    ans[ss][0]=edge[j].from-n;                    ans[ss][1]=edge[j].to;                    ans[ss++][2]=edge[j].flow;                }            }        printf(" %d\n",ss);        for(int i=0;i