http://blog.csdn.net/acmmmm/article/details/11199941
struct Edge{ int from,to,flow,cap, nex; }edge[M*2];//双向边,注意RE 注意这个模版是 相同起末点的边 合并而不是去重 int head[N],edgenum;//2个要初始化-1和0 void addedge(int u,int v,int cap){//网络流要加反向弧 Edge E={u,v,0,cap,head[u]}; edge[edgenum]=E; head[u]=edgenum++; Edge E2={v,u,0,cap,head[v]}; //这里的cap若是单向边要为0 edge[edgenum]=E2; head[v]=edgenum++; } int dis[N],cur[N];//距离起点的距离 cur[i]表示i点正在考虑的边 优化不再考虑已经用过的点 初始化为head bool vis[N]; bool BFS(int Start,int End){ memset(vis,0,sizeof(vis)); memset(dis,-1,sizeof(dis)); queue<int>Q; while(!Q.empty())Q.pop(); Q.push(Start); dis[Start]=0; vis[Start]=1; while(!Q.empty()) { int u = Q.front(); Q.pop(); for(int i=head[u];i!=-1;i=edge[i].nex){ Edge E =edge[i]; if(!vis[E.to] && E.cap>E.flow) { vis[E.to]=1; dis[E.to]=dis[u]+1; if(E.to==End)return true; Q.push(E.to); } } } return false; } int DFS(int x, int a,int End){//流入x 的流量是a if(x==End || a==0)return a; int flow = 0, f; for(int& i=cur[x];i!=-1;i=edge[i].nex) { Edge& E = edge[i]; if(dis[x]+1 == dis[E.to] && (f = DFS(E.to , Min(a, E.cap-E.flow), End))>0 ) { E.flow += f; edge[ i^1 ].flow -= f;//反向边要减掉 flow += f; a -= f; if(a==0)break; } } return flow; } int Maxflow(int Start,int End){ int flow=0; while(BFS(Start,End)){ memcpy(cur,head,sizeof(head));//把head的数组复制过去 flow += DFS(Start, inf, End); } return flow; }