POJ1273 Drainage Ditches

发表于 | 分类于 |

题目传送门

Description

一次下雨淹了Bessie的田，所以FJ建了个排水系统帮Bessie排水到。

整个排水系统由$N$个点，$M$条排水管道组成。

除起点和终点每个点每的排水量和入水量要一致，时刻每条管道有一个单位时间最大排水量$f$。

Bessie的田就是起点$v_1$，终点是一条小溪点$v_n$。

求整个排水系统单位时间最大排水量。

Input

第一行：两个整数，$M$和$N$，意义如题。

接下来$M$行：每行三个整数，$S$、$E$和$C$，表示点$S$和点$E$之间有条容量为$C$的排水管道。

Output

一行：一个整数，最大排水量。

Solution

网络流裸题

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define oo 1000000000
//#include<
using namespace std;
int m,n,ans;
// in
struct Edge
{
	int ap,v;
	Edge *next,*fe;
}edge[510],*ind[210];
int l=0;
void input(int f,int t,int c)
{
	edge[++l].ap=t;
	edge[l].v=c;
	edge[l].next=ind[f];
	ind[f]=&edge[l];
	
	edge[++l].ap=f;
	edge[l].v=0;
	edge[l].next=ind[t];
	ind[t]=&edge[l];
	
	edge[l].fe=&edge[l-1];
	edge[l-1].fe=&edge[l];
}
//
int q[210],level[210];   //bfs构层次图
bool bfs()
{
	memset(q,0,sizeof(q));
	memset(level,0,sizeof(level));
	int h=1,t=2;
	q[h]=1;
	level[1]=1;
	while(h<t)
	{
		Edge *k=ind[q[h]];
		for(;k!=NULL;k=k->next)
		{
			if(k->v==0||level[k->ap]!=0) continue;
			
			q[t++]=k->ap;
			level[k->ap]=level[ q[h] ]+1;
			
		}
		h++;
	}
	
	return level[m]!=0 ? 1:0;
}
int dfs(int x,int maxin) //找增广路
{
	if(x==m) return maxin;
	int sum=0;
	
	Edge *i=ind[x];
	for(;i!=NULL;i=i->next)
	{
		if(maxin==sum) break;
		if(level[i->ap]<=level[x]||!i->v) continue;
		
		int k=dfs(i->ap,min(maxin-sum,i->v));
		i->v-=k;
		i->fe->v+=k;
		sum+=k;
	}
  	if(sum!=maxin) level[u]=0; //当前弧优化
	return sum;
}
//
int main()
{
	scanf("%d%d",&n,&m);
	int l=1;
	for(int i=1;i<=n;i++)
	{
		int f,t,c;
		scanf("%d%d%d",&f,&t,&c);
		input(f,t,c);
	}
	while(bfs())
		ans+=dfs(1,oo);
	printf("%d",ans);
	return 0;
}