P1345 [USACO5.4] 奶牛的电信Telecowmunication
突然发现 USACO 好喜欢玩谐音梗。
题意就是给定一个无向图，问你要删多少点才能使 s , t s,t s,t 不连通。
注意是删点而不是删边，所以不能直接使用最小割来求。所以考虑变换一下题目模型。
经典 trick：将一个点 a a a 拆成两个点 x a , y a x_a,y_a xa,ya，其中 x a x_a xa 只处理入边， y a y_a ya 只处理出边。对于一条边 ( a , b ) (a,b) (a,b)， y a → x b , y b → x a y_a \to x_b,y_b \to x_a ya→xb,yb→xa 连边权为 + ∞ +\infty +∞。而 x a → y a x_a \to y_a xa→ya 连无向边边权为 1 1 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;
}
)
