水题笔记_codevs 1993 草地排水 [(裸的)最大流]

人一旦浮躁就会失去计划

懵逼的 题目

传送至 Codevs

扯淡的 题解

裸的最大流…没什么可说的…就是今天晚上再看看Dinic吧(最近修仙的时候效率极高smg)…

沙茶的 代码

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
96
97
98
99
100
101
102
103
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#define MAXN (200 + 5)
#define MAXM (200 + 5)
#define INF (10000000 + 5)
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
using namespace std;
struct edg
{
int from;
int to;
int cup;
int next;
int flow;
}b[MAXM * 2];
int cnte = 1;
int g[MAXN];
int a[MAXN];
int p[MAXN];
int s = 1, t;
int n, m;
int ans;
int bfs(int);
void ek();
void adn(int ,int ,int);
int main()
{
scanf("%d%d", &m, &n);
t = n;
int srx, sry, srz;
for (int i = 1; i <= m; i++)
{
scanf("%d%d%d", &srx, &sry, &srz);
adn(srx, sry, srz);
adn(sry, srx, 0);
}
ek();
printf("%d", ans);
return 0;
}
void adn(int f, int t, int c)
{
b[++cnte].next = g[f];
b[cnte].from = f;
b[cnte].to = t;
b[cnte].cup = c;
b[cnte].flow = 0;
g[f] = cnte;
}
void ek()
{
while(true)
{
memset(a, 0, sizeof(a));
memset(p, 0, sizeof(p));
int z = bfs(s);
if (!z) break;
ans += z;
for (int i = t; i != s; i = b[p[i]].from)
{
b[p[i]].flow += z;
b[p[i] ^ 1].flow -= z;
}
}
}
int bfs(int s)
{
queue<int> q;
q.push(s);
int dq;
a[s] = INF;
while(!q.empty())
{
dq = q.front();
q.pop();
for (int i = g[dq]; i; i = b[i].next)
{
int dqto = b[i].to;
if (!a[dqto] && (b[i].cup > b[i].flow))
{
a[dqto] = min(a[dq], (b[i].cup - b[i].flow));
p[dqto] = i;
q.push(dqto);
}
}
if (a[t])
break;
}
return a[t];
}
/*
5 4
1 2 40
1 4 20
2 4 20
2 3 30
3 4 10
*/

By 啥都不会的 Cansult