Drainage Ditches
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 13064 Accepted Submission(s):
6196
Problem Description
Every time it rains on Farmer John's fields, a pond
forms over Bessie's favorite clover patch. This means that the clover is covered
by water for awhile and takes quite a long time to regrow. Thus, Farmer John has
built a set of drainage ditches so that Bessie's clover patch is never covered
in water. Instead, the water is drained to a nearby stream. Being an ace
engineer, Farmer John has also installed regulators at the beginning of each
ditch, so he can control at what rate water flows into that ditch.
Farmer
John knows not only how many gallons of water each ditch can transport per
minute but also the exact layout of the ditches, which feed out of the pond and
into each other and stream in a potentially complex network.
Given all this
information, determine the maximum rate at which water can be transported out of
the pond and into the stream. For any given ditch, water flows in only one
direction, but there might be a way that water can flow in a circle.
forms over Bessie's favorite clover patch. This means that the clover is covered
by water for awhile and takes quite a long time to regrow. Thus, Farmer John has
built a set of drainage ditches so that Bessie's clover patch is never covered
in water. Instead, the water is drained to a nearby stream. Being an ace
engineer, Farmer John has also installed regulators at the beginning of each
ditch, so he can control at what rate water flows into that ditch.
Farmer
John knows not only how many gallons of water each ditch can transport per
minute but also the exact layout of the ditches, which feed out of the pond and
into each other and stream in a potentially complex network.
Given all this
information, determine the maximum rate at which water can be transported out of
the pond and into the stream. For any given ditch, water flows in only one
direction, but there might be a way that water can flow in a circle.
Input
The input includes several cases. For each case, the
first line contains two space-separated integers, N (0 <= N <= 200) and M
(2 <= M <= 200). N is the number of ditches that Farmer John has dug. M is
the number of intersections points for those ditches. Intersection 1 is the
pond. Intersection point M is the stream. Each of the following N lines contains
three integers, Si, Ei, and Ci. Si and Ei (1 <= Si, Ei <= M) designate the
intersections between which this ditch flows. Water will flow through this ditch
from Si to Ei. Ci (0 <= Ci <= 10,000,000) is the maximum rate at which
water will flow through the ditch.
first line contains two space-separated integers, N (0 <= N <= 200) and M
(2 <= M <= 200). N is the number of ditches that Farmer John has dug. M is
the number of intersections points for those ditches. Intersection 1 is the
pond. Intersection point M is the stream. Each of the following N lines contains
three integers, Si, Ei, and Ci. Si and Ei (1 <= Si, Ei <= M) designate the
intersections between which this ditch flows. Water will flow through this ditch
from Si to Ei. Ci (0 <= Ci <= 10,000,000) is the maximum rate at which
water will flow through the ditch.
Output
For each case, output a single integer, the maximum
rate at which water may emptied from the pond.
rate at which water may emptied from the pond.
Sample Input
5 4
1 2 40
1 4 20
2 4 20
2 3 30
3 4 10
Sample Output
50
题意：约翰要修水渠，总共有n条边，m个节点，问能够达到的最大流量是多少，1是源点m是汇点；
#include<stdio.h>
#include<string.h>
#include<stack>
#include<queue>
#include<algorithm>
#define MAX 1100
#define MAXM 40010
#define INF 0x7fffff
using namespace std;
struct node
{
int from,to,cap,flow,next;
}edge[MAXM];
int n,f,d,m;
int ans,head[MAX];
int vis[MAX];//用bfs求路径时判断当前点是否进队列，
int dis[MAX];//当前点到源点的距离
int cur[MAX];//保存该节点正在参加计算的弧避免重复计算
void init()
{
ans=0;
memset(head,-1,sizeof(head));
}
void add(int u,int v,int w)
{
node E1={u,v,w,0,head[u]};
edge[ans]=E1;
head[u]=ans++;
node E2={v,u,0,0,head[v]};
edge[ans]=E2;
head[v]=ans++;
}
void getmap()
{
int a,b,c,i;
while(n--)
{
scanf("%d%d%d",&a,&b,&c);
add(a,b,c);
}
}
int bfs(int beg,int end)
{
int i;
memset(vis,0,sizeof(vis));
memset(dis,-1,sizeof(dis));
queue<int>q;
while(!q.empty())
q.pop();
vis[beg]=1;
dis[beg]=0;
q.push(beg);
while(!q.empty())
{
int u=q.front();
q.pop();
for(i=head[u];i!=-1;i=edge[i].next)//遍历所有的与u相连的边
{
node E=edge[i];
if(!vis[E.to]&&E.cap>E.flow)//如果边未被访问且流量未满继续操作
{
dis[E.to]=dis[u]+1;//建立层次图
vis[E.to]=1;//将当前点标记
if(E.to==end)//如果当前点搜索到终点则停止搜索 返回1表示有从原点到达汇点的路径
return 1;
q.push(E.to);//将当前点入队
}
}
}
return 0;//返回0表示未找到从源点到汇点的路径
}
int dfs(int x,int a,int end)//把找到的这条边上的所有当前流量加上a（a是这条路径中的最小残余流量）
{
//int i;
if(x==end||a==0)//如果搜索到终点或者最小的残余流量为0
return a;
int flow=0,f;
for(int& i=cur[x];i!=-1;i=edge[i].next)//i从上次结束时的弧开始
{
node& E=edge[i];
if(dis[E.to]==dis[x]+1&&(f=dfs(E.to,min(a,E.cap-E.flow),end))>0)//如果
{//bfs中我们已经建立过层次图，现在如果 dis[E.to]==dis[x]+1表示是我们找到的路径
//如果dfs>0表明最小的残余流量还有，我们要一直找到最小残余流量为0
E.flow+=f;//正向边当前流量加上最小的残余流量
edge[i^1].flow-=f;//反向边
flow+=f;//总流量加上f
a-=f;//最小可增流量减去f
if(a==0)
break;
}
}
return flow;//所有边加上最小残余流量后的值
}
int Maxflow(int beg,int end)
{
int flow=0;
while(bfs(beg,end))//存在最短路径
{
memcpy(cur,head,sizeof(head));//复制数组
flow+=dfs(beg,INF,end);
}
return flow;//最大流量
}
int main()
{
int i,j;
while(scanf("%d%d",&n,&m)!=EOF)
{
init();
getmap();
printf("%d\n",Maxflow(1,m));
}
return 0;
}