学步园

网络流问题 详解

nuaa 上的1044

#include<iostream><br /> #include<cstring><br /> #include<queue><br /> #include<stdio.h><br /> using namespace std;<br /> #define MAX 405<br /> #define INT_MAX 999999<br /> int g[MAX][MAX];<br /> int flow[MAX],father[MAX],visit[MAX],a[MAX];<br /> int N,F,D;<br /> void init(){<br /> scanf("%d%d%d",&N,&F,&D);<br /> int i,F_i,D_i,j,f,d;<br /> for(i=1;i<=F;++i){<br /> g[0][i]=1;<br /> }<br /> for(i=1;i<=N;++i){<br /> scanf("%d%d",&F_i,&D_i);<br /> for(j=0;j<F_i;++j){<br /> scanf("%d",&f);<br /> g[f][i+F]=1;<br /> }<br /> for(j=0;j<D_i;++j){<br /> scanf("%d",&d);<br /> g[F+N+i][F+2*N+d]=1;<br /> }<br /> }<br /> for(i=1;i<=N;++i){<br /> g[F+i][F+N+i]=1;<br /> }<br /> for(j=1;j<=D;++j){<br /> g[F+2*N+j][F+2*N+D+1]=1;<br /> }<br /> }<br /> int ford_fulkerson(int s,int t)<br /> {<br /> queue<int>Q; int Maxflow=0;<br /> int u,v;<br /> while(1)<br /> {<br /> memset(flow,0,sizeof(flow)); //每次寻找增广路径都将每个点的流入容量置为0<br /> memset(visit,0,sizeof(visit));<br /> flow[s]=INT_MAX; //源点的容量置为正无穷<br /> Q.push(s);<br /> while(!Q.empty()){<br /> u=Q.front();<br /> Q.pop();<br /> for(v=0;v<=t;v++){<br /> if(!visit[v]&&g[u][v]>0){<br /> visit[v]=1;<br /> father[v]=u;<br /> Q.push(v);<br /> //当前点的容量为父亲点容量与边流量的较小者<br /> flow[v]=(flow[u]<g[u][v]? flow[u]:g[u][v]);<br /> }<br /> }<br /> //如果找到了汇点并且汇点容量不为0则清空队列。<br /> if(flow[t]>0)<br /> {<br /> while(!Q.empty())<br /> Q.pop();<br /> break;<br /> }<br /> }<br /> //已经找不到到汇点的增光路经了，就退出整个循环<br /> if(flow[t]==0) break;<br /> for(int i=t;i!=s;i=father[i])<br /> {<br /> g[father[i]][i]-=flow[t]; //正向更新<br /> g[i][father[i]]+=flow[t]; //反向更新<br /> }<br /> Maxflow+=flow[t];<br /> }<br /> return Maxflow;<br /> }<br /> int main(int argc, char *argv[])<br /> {<br /> init();int s=0,t=F+D+2*N+1;<br /> cout<<ford_fulkerson(s,t)<<endl;<br /> return 0;<br /> }<br />