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