<span style="font-size: 18pt; font-family: Arial, Helvetica, sans-serif; background-color: rgb(255, 255, 255);">Drainage Ditches</span>
| Time Limit: 1000MS | Memory Limit: 10000K | |
| Total Submissions: 54939 | Accepted: 20946 |
Description
Input
Output
Sample Input
5 4 1 2 40 1 4 20 2 4 20 2 3 30 3 4 10
Sample Output
50
给出关键部分伪代码来介绍一下网络流的标号法：
- Repeat
- 队列置空；
- 所有点设为未标号；
- 将源点加入队列，并标号为（0，+∞）；
- while 队列非空
- {
- 头指针+1
- 依次检查与头指针指向的元素相连的边
- if 另一点没有标号 and 流量可改进
- {
- 尾指针+1,该点入队
- a[另一点]<-队列头指针元素
- b[另一点]<-Min{b[头指针元素],边的最大流量};
- }
- }
- if 汇点已标号
- {
- 从汇点出发依次修改各条边的流量
- }
- Until 汇点未标号；
- 答案<-所有与汇点相连的边的流量
EK算法：是一种最短路径增值的算法，通过不断从源点广搜寻找最短路径，然后记录路径中的最小容量，再给这条路径上的边上flow增值，（增值之后当然会有一部分边是满流的，那么再次广搜的时候当然也就不能正向搜索到此边了，这条路径上的边的流量都增大了，容量不变，可增值量当然也就会减少），直到从源点广搜不到汇点为止，来实现最大流。由于每次都要广搜所以时间复杂度会达到O（m*m+n）,m为边的个数，n为点的个数。#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<string.h>
#include<queue>
#include<limits.h>
#define MAX 250
using namespace std;
int cap[MAX][MAX];
int m;
int EKarp(int s,int t)
{
queue<int> Q;
int flow[MAX][MAX],a[MAX],u,v,f,pre[MAX];
f=0;
memset(flow,0,sizeof(flow));
while(1)
{
Q.push(s);
memset(a,0,sizeof(a));
a[s]=INT_MAX;
while(!Q.empty())
{
u=Q.front();
Q.pop();
for(v=1;v<=m;v++)
if(!a[v]&&cap[u][v]>flow[u][v])
{
Q.push(v);
a[v]=a[u]<cap[u][v]-flow[u][v]?a[u]:cap[u][v]-flow[u][v];
pre[v]=u;
}
}
if(a[t]==0)break;
for(u=t;u!=s;u=pre[u])
{
flow[pre[u]][u]+=a[t];
flow[u][pre[u]]-=a[t];
}
f+=a[t];
}
return f;
}
int main()
{
int from,to,c,n,ans;
while(~scanf("%d%d",&n,&m))
{
memset(cap,0,sizeof(cap));
while(n--)
{
scanf("%d%d%d",&from,&to,&c);
cap[from][to]+=c;
}
ans=EKarp(1,m);
printf("%d\n",ans);
}
return 0;
}
poj 1273 Drainage Ditches,布布扣,bubuko.com
原文：http://blog.csdn.net/jiangx1994/article/details/37908779