【Poj1273】网络流模版题Drainage Ditches

来源和评测点

USACO 1993
Poj1273
Syzoj11772
Hdu1532
Caioj1115

题目

【题目大意】
有N条水渠,及M个池塘
给出M条水渠所连接的池塘和所能流过的水量(有向)
求水渠1到水渠M中所能流过的水的最大容量

(Caioj上先池塘后水渠)
(Hdu上多组数据)
【输入格式】
第1行:2个整数N(0<=N<=200)和M(2<=M<=200)
接下来M行: 每行有三个整数:x,y,c
表示一条从点x到点y的有向边,流量为c(0<=c<=10,000,000)
【输出格式】
输出一个整数,即最大流量。
【输入样例1】
5 4
1 2 40
1 4 20
2 4 20
2 3 30
3 4 10
【输出样例1】
50

理论上可以卡最短路的数据
【输入样例2】
4 4
1 2 10
2 4 5
2 3 20
3 4 10
【输出样例2】
10

分析

网络流教程和题目分类参见:
【OI之路】03图论算法-4网络流
其他网络流题目参见:Tag-网络流

模板题

代码

我的代码n是点数

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
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int mymin(int x,int y) {return x<y?x:y;}
const int MAXN=210;
const int INF=0x3f3f3f3f;
struct pt
{
int h;
int hou;
}p[MAXN];
struct nod
{
int y,c,g;
}e[MAXN*2];
int ln;
void ins(int x,int y,int c)
{
ln++;
e[ln].y=y;e[ln].c=c;
e[ln].g=p[x].hou;p[x].hou=ln;
}
int n;
int lst[MAXN];
int st,ed;
bool bfs()
{
for(int i=1;i<=n;i++) p[i].h=0;
int tou=1,wei=1;
lst[1]=st;p[1].h=1;
while(tou<=wei)
{
int x=lst[tou];
for(int k=p[x].hou;k>0;k=e[k].g)
{
int y=e[k].y;
if(p[y].h==0 and e[k].c>0)
{
p[y].h=p[x].h+1;
lst[++wei]=y;
}
}
tou++;
}
return p[ed].h>0;
}
int getoth(int k)
{
return k%2==0?k-1:k+1;
}
int dfs(int x,int f)
{
if(x==ed) return f;
int t=0;
for(int k=p[x].hou;k>0;k=e[k].g)
{
int y=e[k].y;
if(p[y].h==p[x].h+1 and e[k].c>0 and t<f)
{
int tt=dfs(y,mymin(e[k].c,f-t));
t+=tt;e[k].c-=tt;e[getoth(k)].c+=tt;
}
}
return t;
}
int main()
{
int m;scanf("%d%d",&m,&n);ln=0;
for(int i=1;i<=m;i++)
{
int x,y,c;
scanf("%d%d%d",&x,&y,&c);
ins(x,y,c);ins(y,x,0);//反向弧
}
st=1;ed=n;
int ans=0;
while(bfs()) ans+=dfs(st,INF);
printf("%d",ans);
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.cf/posts/9eca.html
转载请注明出处,谢谢!

哪怕是一杯奶茶,也将鼓励我继续创作!
0%