水题笔记_ 奶牛隐藏 [网络流, 最大流, 二分, 翻车]

听说二分答案与网络流更配哦

懵逼的 题目

传送至 Luogu

扯淡的 题解

Emmmmm…补去年的坑…

当时SLR(Orzzzzz)拉我做这个题…我直接费用流挑最大费用…WAWAWAWAWA….

Emmmmm…现在一看还是挺显然的二分答案的…

floyd求出两两点之间的最短距离, 拆点, 把每一片田地都拆成$A, B$两个, 二分答案ans, 枚举所有点对, 如果$dis(x,\, y) \le ans$, 就从$A_x$向$B_y$连一条容量为INF的边, 然后从$S$向所有的$A_i$连边, 容量为节点$i$初始的奶牛数量, 从每一个$B_i$向$T$连边, 容量为节点$i$可以容纳的奶牛数量, 然后判断最大流是否等于初始所有奶牛的和即可

以奇怪的姿势WA了好几发…

  • 要用LL, 结果输出忘记改成"%lld"
  • dinic的bfs(), 忘记dis[s] = 1

深感药丸

沙茶的 代码

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
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#define MAXN (100000 + 5)
#define MAXM (500000 + 5)
#define MAXG (200 + 5)
#define INF (10000000000000ll)
#define bh(a) ((a) + 500)
#define rev(a) ((((a) - 1) ^ 1) + 1)
#define LL long long
#define int LL
const int s = 0, t = MAXN - 1;
using namespace std;
struct edg
{
int from, to, next, cap, flow;
edg() {}
edg(int fr, int dqt, int ne, int ca): from(fr), to(dqt), next(ne), cap(ca), flow(0) {}
}b[MAXM << 1];
int g[MAXN], cntb, dis[MAXN], ncow[MAXN], nspa[MAXN], n, m, gx[MAXG][MAXG];
void adn(int from, int to, int cap)
{
b[++cntb] = edg(from, to, g[from], cap);
g[from] = cntb;
}
inline int min(const int x, const int y)
{ return (x < y ? x : y); }
int dinic(int dq, int maxf)
{
if (dq == t || !maxf)
return maxf;
int re = 0;
for (int i = g[dq]; i; i = b[i].next)
if (b[i].cap > b[i].flow && dis[b[i].to] == dis[dq] + 1)
{
int zl = dinic(b[i].to, min(b[i].cap - b[i].flow, maxf));
maxf -= zl;
b[i].flow += zl;
b[rev(i)].flow -= zl;
re += zl;
}
return re;
}
int bfs()
{
memset(dis, 0, sizeof(dis));
queue<int> q;
q.push(s);
dis[s] = 1; // 好像忘记写这个了...
while (!q.empty())
{
int dq = q.front();
q.pop();
for (int i = g[dq]; i; i = b[i].next)
if (b[i].cap > b[i].flow && !dis[b[i].to])
dis[b[i].to] = dis[dq] + 1, q.push(b[i].to);
}
return dis[t];
}
int solve()
{
int re = 0;
while (bfs())
re += dinic(s, INF);
return re;
}
void floyed()
{
for (int k = 1; k <= n; k++)
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (gx[i][k] < INF && gx[k][j] < INF && i != j && j != k && i != k)
gx[i][j] = min(gx[i][j], gx[i][k] + gx[k][j]);
}
void init(int cap)
{
memset(g, 0, sizeof(g));
cntb = 0;
for (int i = 1; i <= n; i++)
{
adn(s, i, ncow[i]);
adn(i, s, 0);

adn(bh(i), t, nspa[i]);
adn(t, bh(i), 0);
for (int j = 1; j <= n; j++)
if (gx[i][j] <= cap)
{
adn(i, bh(j), INF);
adn(bh(j), i, 0);
}
}
}
int ef()
{
int le = 0, ri = INF, ans = -1;
while (le < ri)
{
int mi = (le + ri) >> 1;
init(mi);
if (solve() == ncow[0])
ans = mi, ri = mi;
else
le = mi + 1;
}
return ans;
}
main()
{
freopen("in.in", "r", stdin);
scanf("%lld%lld", &n, &m);
for (int i = 1; i <= n; i++)
scanf("%lld%lld", &ncow[i], &nspa[i]), ncow[0] += ncow[i];
memset(gx, 0x7f, sizeof(gx));
for (int i = 1; i <= n; i++) gx[i][i] = 0;

for (int i = 1; i <= m; i++)
{
int srx, sry, srz;
scanf("%lld%lld%lld", &srx, &sry, &srz);
gx[srx][sry] = gx[sry][srx] = min(srz, gx[sry][srx]);
}
floyed();
printf("%lld", ef());
return 0;
}

/*
3 4
7 2
0 4
2 6
1 2 40
3 2 70
2 3 90
1 3 120
*/

By 沙茶的 Cansult