在讨论问题之前先说一句,如果你这题WA了很久,请先看以下一句话,或许可以省下你翻遍全文的时间:
注意考虑重边。(是不是想大呼[Bi~]?传送门:http://poj.org/problem?id=1273)
嗯,接下来神犇们都走了,继续本文的主题。
一、网络和流(network-flows)
首先,什么是网络流呢?
根据中国人咬文嚼字的习惯,我们把它拆成“网络”和“流”两个概念。
网络:你可以认为这就是一个有向图,只不过有两个特殊的点:源点和汇点,分别只有出边和只有入边。
流:我们把网络上的每条边看做管子,它的边权看做管子单位时间内可以通过个流量,那么单位时间内从源点到汇点通过的流量就称作这个网络的一个流。在一个合法的流中,除了源点和汇点之外,每个节点入边的流量等于出边的流量,这就是流守恒(Flow Conservation)。
约定:c(u,v)表示u节点到v节点的容量,f(u,v)表示u节点到v节点的流量(注意:容量是网络的性质,是不可变的,而流量是一个动态的概念,不同的流下对于相同的边可能有不同的流量),G=(V,E,C)为整个网络。
性质:
1、容量限制:f(u,v) <= c(u,v)
2、反对称性:f(u,v) == -f(v,u)
3、流量守恒:∑f(u,v) == 0(v∈V)
二、剩余网络(residual capacity)和增广路(augment path)
剩余网络:指一个网络中已经有了一个流(可以为0),在原网络的容量基础上减去已经被“占用”的容量所得到的网络。
约定:r(u,v)表示u节点到v节点的剩余流量,即r(u,v) == c(u,v) - f(u,v),由“流量限制”可得r(u,v) >= 0(注意:容量并不满足反对称性,所以规定不存在的边容量为0)。
增广路:如果在剩余网络中可以找到一条从源点到汇点的路径,满足所经过的边的剩余容量都严格大于0(注意这是剩余网络中的边),那么这条路径叫做剩余网络中的一条增广路。
三、题目解答
先贴代码:
1 /* 2 Problem: POJ1273 3 Author: DUSH 4 Algorithm: worknet-flows 5 */ 6 #include<ctime> 7 #include<cstdio> 8 #include<cstring> 9 #include<cstdlib> 10 #include<algorithm> 11 #include<queue> 12 13 #define file(f) freopen(f".in","r",stdin); freopen(f".out","w",stdout) 14 15 using namespace std; 16 const int maxn = 200 + 10; 17 const int data = 10000010; 18 19 int c[maxn][maxn],n,m,p[maxn];//n很小,就开二维数组吧,操作方便些 20 21 void init(){ 22 memset(c,0,sizeof(c));//记得清空数组 23 int u,v,w; 24 for(int i = 1;i <= n;++ i){ 25 scanf("%d%d%d",&u,&v,&w); 26 c[u][v] += w;//防止出现重边 27 } 28 } 29 30 bool spfa(int s,int t){ 31 bool in[maxn];//记录点是否在队列中 32 int dis[maxn];//记录所有点到源点的距离 33 memset(in,0,sizeof(in)); 34 memset(dis,-1,sizeof(dis)); 35 memset(p,-1,sizeof(p)); 36 dis[s] = 0; 37 queue<int> Q; 38 Q.push(s); 39 in[s] = 1; 40 while(!Q.empty()){ 41 int node = Q.front(); 42 if(node == t) break;//找到汇点就退出 43 Q.pop(); 44 in[node] = 0; 45 for(int i = 1;i <= m;++ i){ 46 if(i != node){ 47 if(c[node][i] > 0 && (dis[i] > dis[node] + 1 || dis[i] == -1)){ 48 dis[i] = dis[node] + 1;//找无权图的最短路 49 p[i] = node;//记录前驱 50 if(!in[i]){ 51 Q.push(i); 52 in[i] = 1; 53 } 54 }//注意这里找路径的时候剩余容量必须严格大于0 55 } 56 } 57 } 58 if(dis[t] == -1)//没找到增广路 59 return false; 60 else 61 return true; 62 } 63 64 void work(){ 65 int ans = 0,tmp; 66 while(spfa(1,m)){ 67 int u = m; 68 tmp = data; 69 while(p[u] != -1){ 70 tmp = min(tmp,c[p[u]][u]);//寻找路径上容量最小的边的容量 71 u = p[u]; 72 } 73 ans += tmp;//加入总答案 74 u = m; 75 while(p[u] != -1){ 76 c[p[u]][u] -= tmp; 77 c[u][p[u]] += tmp;//注意这个细节,增加反向边的容量,反例如下图 78 u = p[u]; 79 }//沿途修改剩余网络的容量 80 } 81 printf("%d\n",ans); 82 } 83 84 int main(){ 85 #ifndef ONLINE_JUDGE 86 file("1273"); 87 #endif 88 while(scanf("%d%d",&n,&m) != EOF){ 89 init(); 90 work(); 91 } 92 return 0; 93 }
说到为什么要增加反向边的容量,举个例子就知道了:
有这样一张图(1为源点,6为汇点):
如果不加反向边,第一次增广的结果会是这样(红色为变化后的c值,橙色表示增广路):
由上图得出最大流为2;
若加了反向边(绿色),第一次增广会是这样:
接下来进行第二次增广:
于是我们发现此时得到的最大流为3,如果手推也会得到这个答案。
这是为什么呢?
仔细观察之后会发现,这里其实出现了“分流”的情况,第一次增广时可以认为2节点处2单位的流量分别流向了3和5各一单位,而4节点处的流量则全部经过5节点流到汇点。然而在寻找最短路作为增广路时,我们并不能保证给出的边一定按照了1→2→3...的顺序,所以加上反向边相当于给了我们的程序“反悔”的机会,这时沿反向边的第二次增广就可以认为在5节点处把原本流经5节点的1单位的流量“挤”了上去走2→3→6的路径,也就是第二次增广出来的路径,反向边的容量就是可以“反悔”的剩余量,于是问题就圆满解决了。