题目描述: 

　　正如你所知道的，ACM 竞赛中所有竞赛队伍使用的计算机必须是相同的，以保证参赛者在公平的环境下竞争。这就是所有这些计算机都是同一个厂家生产的原因。 每台ACM 计算机包含P 个部件，当所有这些部件都准备齐全后，计算机就可以组装了，组装好以后就可以交给竞赛队伍使用了。计算机的生产过程是全自动的，通过N 台不同的机器来完成。每台机器从一台半成品计算机中去掉一些部件，并加入一些新的部件（去除一些部件在有的时候是必须的，因为计算机的部件不能以任意的顺序组装）。每台机器用它的性（每小时组装多少台计算机）、输入/输出规格来描述。 

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

输出规格描述了该机器组装的结果。输出规格也是由P 个整数组成，每个整数取值为0 或1，其中0 代表该部件没有生产好，1 代表该部件生产好了。 机器之间用传输速度非常快的流水线连接，部件在机器之间传送所需的时间与机器生产时间相比是十分小的。 

经过多年的运转后，ACM 计算机工厂的整体性能已经远远不能满足日益增长的竞赛需求。因此ACM 董事会决定升级工厂。升级工厂最好的方法是重新调整流水线。ACM 董事会决定让你来解决这个问题。

求大最流，然后输出机器之间流量增加的边

思路：

网络流模型：

1) 添加一个原点S,S提供最初的原料 00000...

2) 添加一个汇点T, T接受最终的产品 11111...

3) 将每个机器拆成两个点: 编号为i的接收节点，和编号为i+n的产出节点（n是机器数目），前者用于接收原料，后者用于提供加工后的半成品或成品。这两个点之间要连一条边，容量为单位时间产量Qi

4) S 连边到所有接收 "0000..." 或 "若干个0及若干个2" 的机器，容量为无穷大

5) 产出节点连边到能接受其产品的接收节点，容量无穷大

6) 能产出成品的节点，连边到T，容量无穷大。

7) 求S到T的最大流

 

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          const int MAXN= 110;//最大顶点数const int MAXM = 11000;//最大边数const int INF=0x3f3f3f3f;using namespace std;vector
          
           
            
              > >pi;int n,s,t,N;struct Edge{ int to,next,cap,flow;}edges[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){ edges[tot].to=v; edges[tot].cap=c; edges[tot].flow=0; edges[tot].next=head[u]; head[u]=tot++; edges[tot].to=u; edges[tot].cap=0; edges[tot].flow=0; edges[tot].next=head[v]; head[v]=tot++;}void bfs(){ memset(d,-1,sizeof(d)); memset(gap,0,sizeof(gap)); gap[0]=1; int front=0,rear=0; d[t]=0; que[rear++]=t; while(front!=rear){ int u=que[front++]; for(int i=head[u];i!=-1;i=edges[i].next){ int v=edges[i].to; if(d[v]!=-1) continue; que[rear++]=v; d[v]=d[u]+1; gap[d[v]]++; } }}int isap(){ bfs(); memcpy(cur,head,sizeof(head)); int top=0,x=s,flow=0; while(d[s]
             
              edges[p[i]].cap-edges[p[i]].flow){ Min=edges[p[i]].cap-edges[p[i]].flow; inser=i; } } for(int i=0;i
              
               edges[i].flow&&d[v]+1==d[x]){ ok=1; cur[x]=i; p[top++]=i; x=edges[i].to; break; } } if(!ok){ int Min=N; for(int i=head[x];i!=-1;i=edges[i].next){ if(edges[i].cap>edges[i].flow&&d[edges[i].to]
               
                0){ cnt++; pi.push_back(make_pair(u-n,make_pair(v,e.flow))); } } } printf(" %d\n",cnt); for(int i=0;i