学步园

最大流模型为有N个湖（点），他们有小溪相连（边），每个小溪都有它们单位时间的最大流量，最大流求的是一个湖（源点）到另一个湖（汇点）单位时间内能流入的最大流量。

求最大流的一个算法为 ford_fulkerson算法，算法思想：

1.从源点开始寻找一条路径到汇点，记录这条路径流量最小的边的流量为m,然后最大流量+=m，然后每条边的流量都减去m，然后反向更新流量（每条边反方向的流量加上m）；

2.重复步骤1直到找不到路径到汇点为止，最终的最大流量即为所求的最大流。

ford_fulkerson C++模板：

void ford_fulkerson(int s,int e)<br /> {<br /> queue<int>Q;<br /> int u,v;<br /> while(1)<br /> {<br /> Maxflow=0;//最大流初始化<br /> memset(maxflow,0,sizeof(maxflow));//每次寻找增广路径都将每个点的流入容量置为0<br /> memset(visit,0,sizeof(visit));//标记一个点是否已经压入队列<br /> maxflow[s]=INT_MAX;//源点的容量置为正无穷<br /> Q.push(s); // 将源点压入队列<br /> while(!Q.empty()) //当队列不为空<br /> {<br /> u=Q.front();<br /> Q.pop();<br /> for(v=1;v<=N;v++)<br /> {<br /> if(!visit[v]&&flow[u][v]>0)<br /> {<br /> visit[v]=1;<br /> father[v]=u;//记录下他的父亲方便往后的正反向更新<br /> Q.push(v);<br /> maxflow[v]=(maxflow[u]<flow[u][v]?maxflow[u]:flow[u][v]);//当前点的容量为父亲点容量与边流量的较小者<br /> }<br /> }<br /> if(maxflow[e]>0) //如果找到了汇点并且汇点容量不为0则清空队列。<br /> {<br /> while(!Q.empty())<br /> Q.pop();<br /> break;<br /> }<br /> }<br /> if(maxflow[e]==0)//已经找不到到汇点的增光路经了，就退出整个循环<br /> break;<br /> for(i=e;i!=s;i=father[i])<br /> {<br /> flow[father[i]][i]-=maxflow[e];//正向更新<br /> flow[i][father[i]]+=maxflow[e];//反向更新<br /> }<br /> Maxflow+=maxflow[e];//更新最大流<br /> }<br /> }

一个证明需要反向更新的例子：

这个图从1到6明显最的流量为3+3=6，但如果不用反向更新，由于用BFS首先找到一条路径1-2-3-6，然后1-2,2-3,3-6这几条边被更新成了0，就再也找不到增广路径到6了，而1-5-3的剩余的5个流量就无路可走了，用反向更新会再在3-2这里加一条流量为3的边，这时候1-5-3的5流量就可以通过这条边到2再到4再到6了，这就是反向更新的需要。

最大流题目：

POJ1273

最大流入门题，代码：

#include<iostream><br /> #include<queue><br /> using namespace std;<br /> const int MAXN = 205;<br /> const int maxint = 0x3f3f3f3f;<br /> int flow[MAXN][MAXN],maxflow[MAXN],father[MAXN];<br /> int i,Maxflow,M,visit[MAXN];<br /> void ford_fulkerson()<br /> {<br /> queue<int>Q;<br /> int u,v;<br /> while(1)<br /> {<br /> memset(maxflow,0,sizeof(maxflow));<br /> memset(visit,0,sizeof(visit));<br /> maxflow[1]=INT_MAX;<br /> Q.push(1);<br /> while(!Q.empty())<br /> {<br /> u=Q.front();<br /> Q.pop();<br /> for(v=1;v<=M;v++)<br /> {<br /> if(!visit[v]&&flow[u][v]>0)<br /> {<br /> visit[v]=1;<br /> father[v]=u;<br /> Q.push(v);<br /> maxflow[v]=(maxflow[u]<flow[u][v]?maxflow[u]:flow[u][v]);<br /> }<br /> }<br /> if(maxflow[M]>0)<br /> {<br /> while(!Q.empty())<br /> Q.pop();<br /> break;<br /> }<br /> }<br /> if(maxflow[M]==0)<br /> break;<br /> for(i=M;i!=1;i=father[i])<br /> {<br /> flow[father[i]][i]-=maxflow[M];<br /> flow[i][father[i]]+=maxflow[M];<br /> }<br /> Maxflow+=maxflow[M];<br /> }<br /> }<br /> int main()<br /> {<br /> int N,si,ei,ci;<br /> while(cin>>N>>M&&N!=EOF)<br /> {<br /> Maxflow=0;<br /> memset(flow,0,sizeof(flow));<br /> for(i=0;i<N;i++)<br /> {<br /> cin>>si>>ei>>ci;<br /> flow[si][ei]+=ci;<br /> }<br /> ford_fulkerson();<br /> cout<<Maxflow<<endl;<br /> }<br /> return 0;<br /> }<br />

POJ 1459

这题关键是建图，为该图自建一个源点和汇点就行了。。

POJ 1149

 灰常经典，无敌建图题，最大流必做题。

1.增加源点0与汇点t;

2.如果某顾客有某个猪圈的钥匙，如果之前有顾客有这个猪圈的钥匙，那么加一条之前那顾客到当前这个顾客的边，权值为无限大（方便剩下的猪能传递给当前的顾客），否则就在源点0与这个顾客加一条边，权值为这个猪圈的猪数目。还需要加一条该顾客到汇点t的边，权值为该顾客的需要猪的数量。

3.求源点0到汇点t的最大流