P1345 [USACO5.4] 奶牛的电信Telecowmunication

P1345 [USACO5.4] 奶牛的电信Telecowmunication

突然发现 USACO 好喜欢玩谐音梗。

题意就是给定一个无向图，问你要删多少点才能使 $s,t$ 不连通。

注意是删点而不是删边，所以不能直接使用最小割来求。所以考虑变换一下题目模型。

经典 trick：将一个点 $a$ 拆成两个点 $x_a,y_a$，其中 $x_a$ 只处理入边，$y_a$ 只处理出边。对于一条边 $(a,b)$，$y_a\to x_b,y_b\to x_a$ 连边权为 $+\infty$。而 $x_a\to y_a$ 连无向边边权为 $1$。

这样就发现可以使用最小割处理了！

直接把板子粘过来即可。

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n, m;
const int N = 210;struct edge {int to, val;int id;
};
vector<edge> v[N];
int d[N];void add(int x, int y, int val) {v[x].push_back({y, val, v[y].size()});v[y].push_back({x, 0, v[x].size() - 1});
}void bfs(int s) {memset(d, -1, sizeof d);queue<int> q;q.push(s), d[s] = 0;while (!q.empty()) {int f = q.front();q.pop();for (auto [to, val, id] : v[f])if (d[to] == -1 && val > 0)d[to] = d[f] + 1, q.push(to);}
}
int cur[N];int dfs(int u, int t, int fl) {if (u == t)return fl;for (int i = cur[u]; i < (int)v[u].size(); i = ++cur[u])if (d[v[u][i].to] == d[u] + 1 && v[u][i].val > 0) {int f = dfs(v[u][i].to, t, min(fl, v[u][i].val));if (f > 0) {v[u][i].val -= f, v[v[u][i].to][v[u][i].id].val += f;return f;} elsed[v[u][i].to] = -1;}return 0;
}int dinic(int s, int t) {int ans = 0;while (1) {int x = 0;bfs(s);if (d[t] == -1)break;memset(cur, 0, sizeof cur);while ((x = dfs(s, t, 1e15)) > 0)ans += x;}return ans;
}signed main() {int s, t;ios::sync_with_stdio(0);cin >> n >> m >> s >> t;
//对于一个点 i，x_i 的编号为 i，y_i 的编号为 i + nfor (int i = 1; i <= m; i++) {int x, y;cin >> x >> y;add(x + n, y, 1e9);add(y + n, x, 1e9);//加边}for (int i = 1; i <= n; i++)add(i, i + n, 1), add(i + n, i, 1);//加边cout << dinic(s + n, t) << endl;return 0;
}