381. 有線電視網絡 - AcWing題庫

給定一張?n?個點?m?條邊的無向圖，求最少去掉多少個點，可以使圖不連通。

如果不管去掉多少個點，都無法使原圖不連通，則直接返回?n。

輸入格式

輸入包含多組測試數據。

每組數據占一行，首先包含兩個整數?n?和?m，接下來包含?m?對形如?(x,y) 的數對，形容點?x?與點?y?之間有一條邊。

數對?(x,y) 中間不會包含空格，其余地方用一個空格隔開。

輸出格式

每組數據輸出一個結果，每個結果占一行。

數據范圍

0≤n≤50

輸入樣例：

0 0
1 0
3 3 (0,1) (0,2) (1,2)
2 0
5 7 (0,1) (0,2) (1,3) (1,2) (1,4) (2,3) (3,4)

輸出樣例：

0
1
3
0
2

解析：?

通過刪除某些點讓無向圖不連通。

如果是刪除某些邊使得無向圖不連通，我們很容易想到使用最小割算法將割邊刪去。通過枚舉源點 S 和匯點 T，然后使用最小割算法處理。

但本題要求將點刪除，而非將邊刪除。我們需要將點轉換成邊看看是否能使用最小割算法。

拆點：

使用常見的拆點方式，將點拆成出點和入點，且出點和入點之間連一條邊，邊權為1，對應本題中要求求得點得數量。

簡單割處理：??

由于本題只能刪除點而不能刪除邊，所以我們要使得最小割算法不刪除原圖得邊：將原圖的邊的容量設為正無窮。（最小割算法中的常用技巧，將不希望作為割邊的邊的容量設為正無窮）?

定義簡單割：割邊僅為有限容量的邊形成的割稱為簡單割

?簡單割具體證明參考：2325. 有向圖破壞（二分圖，最小點權覆蓋，最小割，網絡流）-CSDN博客?

證明簡單割與要刪掉的點的點割集存在一一對應的關系：

簡單割=>?點割集
因為我們通過簡單割求出的割邊都是點內部的邊，當我們把簡單割里的邊全刪掉后，源點和匯點則不會聯通了，這些構成“內部邊”的點的集合就是點割集。

下面用反證法證明上面構造出來的點割集一定是符合題意的要刪掉的點：

假設上面構造出來的點割集不符合題意，即把上面所有的點刪掉，在原圖里依然存在從源點到達匯點的路徑，說明在原圖中，存在一條不經過我們構造出來的點割集里的點的路徑即不經過“點內部的邊”，依然能從源點到達匯點，對應到流網絡里則是存在一條從源點到匯點的不經過割邊的路徑，則說明源點與匯點在一個集合里，說明這不是一個割，與前提矛盾。因此反證得證。

點割集=>?簡單割
這里的點割集指的是“極小點割集”

構造簡單割的方法：

從源點開始dfs一遍，若經過點割集里的點，則停下不往前搜，若不是則往前搜，每次把搜到的點打個標記，這樣標記了的點就是S集合，沒有標記的點就是T集合，構成一個簡單割C[S,T]因此我們可以證出簡單割與割點集存在一一對應的關系。

考慮數量關系
由于我們建邊的時候把入點到出點的邊的容量設為1，則得到的簡單割的割邊和就是選到的點的數量，則可以得到：割點集的點的數量 = 簡單割的割的容量和 ，因此：最小割點集 = 最小割

#include<iostream>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<utility>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<math.h>
#include<map>
#include<sstream>
#include<deque>
#include<unordered_map>
#include<unordered_set>
#include<bitset>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
const int N = 1e2 + 10, M = (2500+50) * 2 + 10, INF = 0x3f3f3f3f;
int n, m, S, T;
int h[N], e[M], f[M], ne[M], idx;
int q[N], d[N], cur[N];void add(int a, int b, int c) {e[idx] = b, f[idx] = c, ne[idx] = h[a], h[a] = idx++;e[idx] = a, f[idx] = 0, ne[idx] = h[b], h[b] = idx++;
}bool bfs() {int hh = 0, tt = 0;memset(d, -1, sizeof d);q[0] = S, d[S] = 0, cur[S] = h[S];while (hh <= tt) {int t = q[hh++];for (int i = h[t]; i != -1; i = ne[i]) {int j = e[i];if (d[j] == -1 && f[i]) {d[j] = d[t] + 1;cur[j] = h[j];if (j == T)return 1;q[++tt] = j;}}}return 0;
}int find(int u, int limit) {if (u == T)return limit;int flow = 0;for (int i = cur[u]; i != -1 && flow < limit; i = ne[i]) {int j = e[i];cur[u] = i;if (d[j] == d[u] + 1 && f[i]) {int t = find(j, min(f[i], limit - flow));if (!t)d[j] = -1;f[i] -= t, f[i ^ 1] += t, flow += t;}}return flow;
}int dinic() {int ret = 0, flow;while (bfs())while (flow = find(S, INF))ret += flow;return ret;
}int main() {while (cin >> n >> m) {memset(h, -1, sizeof h);idx = 0;for (int i = 0; i < n; i++) {add(i, i + n, 1);}for (int i = 1,a,b; i <= m; i++) {scanf(" (%d,%d)", &a, &b);add(n + a, b, INF);add(n + b, a, INF);}int ans = n;for (int i = 0; i < n; i++) {for (int j = 0; j < i; j++) {S = n + i, T = j;for (int k = 0; k < idx; k += 2) {f[k] += f[k ^ 1];f[k ^ 1] = 0;}ans = min(ans, dinic());}}cout << ans << endl;}return 0;
}