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;
}