啊？你问最近为啥没有闲话？
嘛，首先是 NOIP 取消了！然后就滚回家搞 whk 了！回家来 whk 之余浅写了点杂东西，反正晚上没事可干（
突然发现句末不想加句号 句中不想加逗号（
主要是这种语气下感觉会很突兀（
于是就用空格和半括号（以及感叹号）代替了！
元气
现在属于是回来复建了（
然后跟进度嘛 今天是网络流（初等）！
我发现写了这些题 Dinic(s,t) 是根本没变化 所以粘在最开始的地方（
流杂题
不粘题面了。
Dinic
#include <bits/stdc++.h>
using namespace std; using pii = pair<int,int>; using vi = vector<int>; using ll = long long;
using ull = unsigned long long; using db = double; using ld = long double; using lll = __int128_t;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
template <typename T> T rand(T l, T r) { return uniform_int_distribution<T>(l, r)(rnd); }
template <typename T1, typename T2> T1 min(T1 a, T2 b) { return a < b ? a : b; }
template <typename T1, typename T2> T1 max(T1 a, T2 b) { return a > b ? a : b; }
#define file(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout)
#define ufile(x)
#define rep(i,s,t) for (register int i = (s), i##_ = (t) + 1; i < i##_; ++ i)
#define pre(i,s,t) for (register int i = (s), i##_ = (t) - 1; i > i##_; -- i)
#define Aster(i, s) for (int i = head[s], v; i; i = e[i].next)
#define all(s) s.begin(), s.end()
#define eb emplace_back
#define pb pop_back
#define em emplace
const int N = 2e6 + 5;
const int inf = 0x3f3f3f3f;
const ll infll = 0x3f3f3f3f3f3f3f3fll;
int head[2][N], mlc = 1;
struct ep {
int to, next, flow;
} e[N << 1];
void adde(int u, int v, int f) {
e[++ mlc] = { v, head[0][u], f };
head[0][u] = mlc;
e[++ mlc] = { u, head[0][v], 0 };
head[0][v] = mlc;
}
queue<int> que;
int dep[N];
bool bfs(int s, int t) {
rep(i,1,M) dep[i] = 0, head[1][i] = head[0][i];
que.push(s); dep[s] = 1;
while (que.size()) {
int u = que.front(); que.pop();
for (int i = head[0][u], v; i; i = e[i].next) {
v = e[i].to;
if (e[i].flow and !dep[v]) {
dep[v] = dep[u] + 1;
que.push(v);
}
}
} return dep[t];
}
int dfs(int u, int in, int t) {
if (u == t) return in;
int out = 0;
for (int &i = head[1][u], v; i; i = e[i].next) {
v = e[i].to;
if (e[i].flow and dep[v] == dep[u] + 1) {
int res = dfs(v, min(in, e[i].flow), t);
if (res == 0) dep[v] = 0;
in -= res, out += res;
e[i].flow -= res, e[i ^ 1].flow += res;
if (in == 0) break;
}
} return out;
}
int Dinic(int s, int t) {
int ret = 0;
while(bfs(s, t)) ret += dfs(s, 1e9, t);
return ret;
}
标准拆出入点模型。
首先每个点的承载力用拆点解决。每个点拆成入点和出点，之间连边，流量是这根石柱能承受的蜥蜴数。然后我们就可以随意连边了，只需要保证指向该点的边连在入点，从该点出去的边连在出点即可。
随后就是显然的关系了。
首先由超级源点向各存在蜥蜴的点连边。然后能跳到的点间互相连边，能跳出去的点向超级汇点连边。
最后最大流就是能跳出去的最大蜥蜴数。
距离是欧氏距离。
code
int n, r, c, d, s, t, cnt, id[25][25][2];
char mat[25][25], pos[25][25];
bool inrange(int x1, int y1, int x2, int y2) {
return (x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1) <= d * d;
}
signed main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin >> r >> c >> d;
rep(i,1,r) cin >> mat[i] + 1;
rep(i,1,r) cin >> pos[i] + 1;
rep(i,1,r) rep(j,1,c) id[i][j][0] = ++ n, id[i][j][1] = ++ n;
s = ++ n, t = ++ n;
rep(i,1,r) rep(j,1,c) if (pos[i][j] == 'L') adde(s, id[i][j][0], 1), ++ cnt;
rep(i,1,r) rep(j,1,c) if (mat[i][j] != 0) adde(id[i][j][0], id[i][j][1], mat[i][j] - '0');
rep(i,1,r) rep(j,1,c) if (i <= d or i >= r - d + 1 or j <= d or j >= c - d + 1) adde(id[i][j][1], t, inf);
rep(i,1,r) rep(j,1,c) rep(i2,1,r) rep(j2,1,c) if (i <= d or i >= r - d + 1 or j <= d or j >= c - d + 1) continue;
else if (inrange(i, j, i2, j2)) adde(id[i][j][1], id[i2][j2][0], inf);
cout << cnt - Dinic(s, t);
}
标准二分判定模型。
我们假定目前需要判定一个时间是否可以将所有机器人都消灭。这时我们就已知了每个激光武器的最大攻击量。换句话说，我们就已知了从超级原点到每一个激光武器对应边的最大流量。
因此可以直接建图跑最大流。
建图显然，源点连向武器，边权二分得到，武器连向能瞄准到的机器人，可以无限输出，然后机器人连向终点，边权是机器人的血条。最后看一下是否最大流是机器人血条加和就行。
输出不要四舍五入。
code
int M, s, t, n, m, a[N], b[N], tot;
bool ck[55][55]; // 5
bool check(double tme) {
rep(i,1,M) head[0][i] = 0; mlc = 1;
rep(i,1,m) adde(s, i, b[i] * tme);
rep(i,1,m) rep(j,1,n) if (ck[i][j]) adde(i, m + j, inf);
rep(j,1,n) adde(m + j, t, a[j]);
return fabs(Dinic(s, t) - tot) <= eps;
}
signed main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin >> n >> m; M = n + m + 2; s = n + m + 1, t = n + m + 2;
rep(i,1,n) cin >> a[i], tot += a[i];
rep(i,1,m) cin >> b[i];
rep(i,1,m) rep(j,1,n) cin >> ck[i][j];
double l = 0, r = 1e4, mid;
while ((r - l) > eps) {
mid = (l + r) / 2;
if (check(mid)) r = mid;
else l = mid;
}
printf("%.6lf", l);
}
P4311 士兵占领
最小 \(\to\) 最大模型。
最少个数的士兵不好最大流。那就转化成最大不放的士兵数。删掉一个士兵会让行列都减一，那让行列分别连在源汇点上，分别流量是该行/列能删掉的最大士兵数。然后在可以删士兵的位置连 \(1\) 的边。跑最大流即可。
总点数减不可以放的位置减跑出来的值就是最终答案。
记得减。
code
int M, s, t, n, m, k, l[N], c[N], t1, t2;
bool ck[105][105];
signed main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin >> m >> n >> k;
rep(i,1,m) cin >> l[i], l[i] = n - l[i];
rep(i,1,n) cin >> c[i], c[i] = m - c[i];
rep(i,1,k) cin >> t1 >> t2, l[t1] --, c[t2] --, ck[t1][t2] = 1;
rep(i,1,m) if (l[i] < 0) puts("JIONG!"), exit(0);
rep(i,1,n) if (c[i] < 0) puts("JIONG!"), exit(0);
s = n + m + 1, t = M = n + m + 2;
rep(i,1,m) adde(s, i, l[i]);
rep(i,1,n) adde(m + i, t, c[i]);
rep(i,1,m) rep(j,1,n) if (!ck[i][j]) adde(i, j + m, 1);
cout << n * m - Dinic(s, t) - k;
}
超级拆点模型。二分 + 拆点、
首先这玩意直接算答案是很麻烦的。因此考虑转换成判定。转成判定有好处：我们能知道每个门能拆出几个点来了。我们将一个门拆成[时间]个点，每个点向出边连 \(1\) 的边，向下一时间的门连 \(\infty\) 的边。这样只需要跑出每个点到每个门的路径长度就可以直接将一个点连在对应门的对应时间上。
跑最大流即可。
听说空间复杂度很大？不是很懂。
code
int M, s, t, n, m, sid[25][25], id[105][105], mx, cnt, pop, dis[25][25][25 * 25];
char gr[105][105], vis[25][25];
int dx[] = {0, 0, -1, 1}, dy[] = {-1, 1, 0, 0};
struct _tmp { int x, y, dis; _tmp(int x, int y, int d) : x(x), y(y), dis(d) {} };
queue<_tmp> q_t;
bool check(int tme) {
rep(i,1,M) head[0][i] = 0; mlc = 1;
M = tme * cnt + pop; s = ++ M, t = ++ M;
rep(i,1,n) rep(j,1,m) if (gr[i][j] == '.') adde(s, sid[i][j], 1);
rep(i,1,cnt) rep(j,1,tme) adde(pop + (i - 1) * tme + j, t, 1);
rep(i,1,cnt) rep(j,1,tme-1) adde(pop + (i - 1) * tme + j, pop + (i - 1) * tme + j + 1, inf);
rep(i,1,n) rep(j,1,m) if (gr[i][j] == '.') rep(k,1,cnt) if (dis[i][j][k] and dis[i][j][k] <= tme)
adde(sid[i][j], pop + (k - 1) * tme + dis[i][j][k], 1);
return Dinic(s, t) == pop;
}
signed main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin >> n >> m;
rep(i,1,n) cin >> gr[i] + 1;
rep(i,1,n) rep(j,1,m) if (gr[i][j] == 'D') id[i][j] = ++ cnt;
rep(i,1,n) rep(j,1,m) if (gr[i][j] == '.') {
sid[i][j] = ++ pop;
q_t.emplace(i, j, 0);
memset(vis, 0, sizeof vis);
vis[i][j] = 1;
while (q_t.size()) {
auto now = q_t.front(); q_t.pop();
if (gr[now.x][now.y] == 'D') dis[i][j][ id[now.x][now.y] ] = now.dis;
else rep(k,0,3) if (1 <= now.x + dx[k] and now.x + dy[k] <= n and 1 <= now.y + dy[k] and now.y + dy[k] <= m)
if (!vis[now.x + dx[k]][now.y + dy[k]] and gr[now.x + dx[k]][now.y + dy[k]] != 'X')
vis[now.x + dx[k]][now.y + dy[k]] = 1, q_t.emplace(now.x + dx[k], now.y + dy[k], now.dis + 1);
}
}
int l = 0, r = 1000, mid;
while (l <= r) {
int mid = l + r >> 1;
if (check(mid)) r = mid - 1;
else l = mid + 1;
} if (r == 1000) puts("impossible");
else cout << r + 1 << '\n';
}
染色经典模型。
首先假设我们将棋盘黑白染色，满足任意四联通的两个格子颜色不同。我们发现，每次肯定是在两个不同色的格子上 \(+1\)。因此如果两种颜色格子的数量相同，则必定有两种颜色格子的初始数字加和相同。假设最终变成的数是 \(x\)，则我们有操作次数是 \(x * [格子的数量] - [初始数字加和]\)。又发现这个 \(x\) 可以二分，因为 \(x\) 可以达到则 \(x + 1\) 可以通过整体 \(+1\) 达到。二分的判定考虑网络流，我们能将黑白点建二分图，点与源汇点连边流量是点还需要操作的次数。随后我们将可以在一次操作中 \(+1\) 的黑白点链接流量无限的边，判定得到的答案是否能将所有点填满即可。
如果两种颜色格子数不相同，我们可以发现 \(x * [黑格子的数量] - [黑格子初始数字加和] = x * [白格子的数量] - [白格子初始数字加和]\)，因为操作数肯定相同。这得到了 \(x = \frac{\text{[初始数字差值]}}{\text{[格子数量差值]}}\)。计算后做一次如上的判定即可。
inf 开大点。
code
int M, s, t, T, n, m, mx, n1, n2, s1, s2;
int a[45][45];
int dx[] = {0, 0, -1, 1}, dy[] = {-1, 1, 0, 0};
bool check(int mxv) {
rep(i,1,M) head[0][i] = 0; mlc = 1;
M = n * m; s = ++ M, t = ++ M;
int val = 0;
rep(i,1,n) rep(j,1,m) {
if ((i + j) & 1) {
adde(s, (i - 1) * m + j, mxv - a[i][j]);
val += mxv - a[i][j];
rep(k,0,3) if (1 <= i + dx[k] and i + dx[k] <= n and 1 <= j + dy[k] and j + dy[k] <= m)
adde((i - 1) * m + j, (i + dx[k] - 1) * m + j + dy[k], inf);
} else adde((i - 1) * m + j, t, mxv - a[i][j]);
}
return val == Dinic(s, t);
}
signed main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin >> T;
while (T--) {
n1 = n2 = s1 = s2 = mx = 0;
cin >> n >> m;
rep(i,1,n) rep(j,1,m) cin >> a[i][j], mx = max(mx, a[i][j]);
rep(i,1,n) rep(j,1,m) {
if ((i + j) & 1) s1 += a[i][j], ++ n1;
else s2 += a[i][j], ++ n2;
}
if (n1 == n2) {
if (s1 != s2) cout << "-1\n";
else {
int l = mx, r = 2e9, mid;
while (l <= r) {
mid = l + r >> 1;
if (check(mid)) r = mid - 1;
else l = mid + 1;
}
if (r == 2e9) cout << "-1\n";
else cout << (r + 1) * n1 - s1 << '\n';
}
} else {
int x = (s1 - s2) / (n1 - n2);
if (x < mx or !check(x)) cout << "-1\n";
else cout << x * n1 - s1 << '\n';
}
}
}
happiness
经典最小割模型。
上一张同样很经典的图（图 from \(\text{FromATP}\)）：
怎么样？会了吧！
我们要求最大贡献，那就转化成全部减最小贡献。
最小不行怎么做？这类题一般是二选一，那就源点表示选 \(1\)，汇点表示选 \(0\)，流量就是选 \(0/1\) 的贡献，每个点直接向源汇点连边。因为一个人不能选两个，这两条边不能都存在，总得删掉一条。这也就想到了最小割。我们割掉一条边表示选这条边对应的状态。
同时我们需要判定“两人共同选”。我们发现，这样总会是把一侧的边全割掉，另一侧都留着。那我们在割掉边的这一侧再拿一个新节点连上两人对应的节点，从这个点再连上割掉边一侧的超级源/汇点。连源汇点的边就设为两人共同选的贡献，这时由于两人共同选，也应该把这部分的贡献加上，这也契合了最小割的理念。
注意……没啥要注意的。
code
int M, s, t, n, m, ans, id[101][101];
int wen[101][101], li[101][101];
int rowwen[101][101], rowli[101][101];
int colwen[101][101], colli[101][101];
signed main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin >> n >> m;
rep(i,1,n) rep(j,1,m) cin >> wen[i][j], ans += wen[i][j];
rep(i,1,n) rep(j,1,m) cin >> li[i][j], ans += li[i][j];
rep(i,1,n-1) rep(j,1,m) cin >> rowwen[i][j], ans += rowwen[i][j];
rep(i,1,n-1) rep(j,1,m) cin >> rowli[i][j], ans += rowli[i][j];
rep(i,1,n) rep(j,1,m-1) cin >> colwen[i][j], ans += colwen[i][j];
rep(i,1,n) rep(j,1,m-1) cin >> colli[i][j], ans += colli[i][j];
s = ++ M, t = ++ M;
rep(i,1,n) rep(j,1,m) {
id[i][j] = ++ M;
adde(s, id[i][j], wen[i][j]);
adde(id[i][j], t, li[i][j]);
}
register int t1, t2, t3, t4;
rep(i,1,n) rep(j,1,m) {
if (i + 1 <= n) {
t1 = id[i][j], t2 = id[i + 1][j], t3 = ++ M, t4 = ++ M;
adde(s, t3, rowwen[i][j]);
adde(t3, t1, inf);
adde(t3, t2, inf);
adde(t1, t4, inf);
adde(t2, t4, inf);
adde(t4, t, rowli[i][j]);
}
if (j + 1 <= m) {
t1 = id[i][j], t2 = id[i][j + 1], t3 = ++ M, t4 = ++ M;
adde(s, t3, colwen[i][j]);
adde(t3, t1, inf);
adde(t3, t2, inf);
adde(t1, t4, inf);
adde(t2, t4, inf);
adde(t4, t, colli[i][j]);
}
}
cout << ans - Dinic(s, t);
}