题目链接

  本题是2004年icpc欧洲区域赛东南欧赛区的题目

题意

  给定一个n（n≤50）个点的无向图，求它的点连通度，即最少删除多少个点，使得图不连通。如下图所示，a）的点连通度为3，b）的点连通度为0，c）的点连通度为2（删除1和2或者1和3）。

分析

  本题可以用最小割模型建图求解，有意思的是，一开始我想出了直接解法：检测当前图是否只有一个连通分量，若不止一个连通分量则不再需要删点，否则找出要删的点并且删除之，答案计数加1。找出当前要删除的点的贪心想法：找到度最小的点后删除其邻接的度最大的那个点（度最小的点有多个时找他们邻接的度最大的那个点删）。
  用最小割模型建图需要拆点，原图每个点拆成入点$i$和出点$i+n$并连容量为1的边$i\to i+n$，对原图每条无向边$(i,j)$，连两条容量为$inf$的边$i+n\to j,j+n\to i$。然后枚举所有的源点$u+n$和汇点$v(0\le u<v<n)$跑最大流，更新最小值作为答案即可。注意跑最大流前每条边的流要先归零。

AC 代码

  直接解法

#include <iostream>
using namespace std;#define N 60
short u[N*N>>1], v[N*N>>1], c[N], cc[N], p[N], g[N][N], n, m;short find(short x) {return p[x]==x ? x : p[x] = find(p[x]);
}short check() {short t = 0;for (short i=0; i<n; ++i) if (c[i]>=0 && find(i)==i) ++t;return t;
}int main() {while (cin >> n >> m) {for (short i=0; i<n; ++i) cc[i] = 0, p[i] = i;for (short i=0; i<m; ++i) {short a, b; char t;cin >> t >> a >> t >> b >> t;g[a][cc[a]++] = b; g[b][cc[b]++] = a;u[i] = a; v[i] = b;p[find(a)] = find(b);}for (short i=0; i<n; ++i) c[i] = cc[i];short ans = 0;while (check() == 1) {++ ans;short cx = N, cy = -1, k;for (short i=0; i<m; ++i) if (c[u[i]]>0 && c[v[i]]>0) {short a = min(c[u[i]], c[v[i]]), b = max(c[u[i]], c[v[i]]);if (a<cx || (a==cx && b>cy)) cx = a, cy = b, k = i;}if (cy < 0) break;short y = c[u[k]] == cy ? u[k] : v[k];for (short i=0; i<cc[y]; ++i) --c[g[y][i]];c[y] = -1;for (short i=0; i<n; ++i) p[i] = i;for (short i=0; i<m; ++i) if (c[u[i]]>0 && c[v[i]]>0) p[find(u[i])] = find(v[i]);}cout << ans << endl;}
}

  网络流法

#include <iostream>
#include <cstring>
using namespace std;#define N 102
struct edge {int u, v, cap, flow;} e[N*N>>1];
int g[N][N>>1], q[N], p[N], d[N], cur[N], num[N], cnt[N], c, m, n; bool vis[N];void add_edge(int u, int v, int cap) {e[c] = {u, v, cap, 0}; g[u][cnt[u]++] = c++; e[c] = {v, u, 0, 0}; g[v][cnt[v]++] = c++;
}bool bfs(int s, int t) {memset(vis, 0, sizeof(vis)); memset(d, 0, sizeof(d)); q[0] = t; d[t] = 0; vis[t] = true;int head = 0, tail = 1;while (head < tail) {int v = q[head++];for (int i=0; i<cnt[v]; ++i) {const edge& ee = e[g[v][i]^1];if (!vis[ee.u] && ee.cap > ee.flow) vis[ee.u] = true, d[ee.u] = d[v] + 1, q[tail++] = ee.u;}}return vis[s];
}int max_flow(int s, int t) {for (int i=0; i<c; ++i) e[i].flow = 0;if (!bfs(s, t)) return 0;memset(num, 0, sizeof(num)); memset(cur, 0, sizeof(cur));int u = s, flow = 0, n1 = n<<1;for (int i=0; i<n1; ++i) ++num[d[i]];while (d[s] < n1) {if (u == t) {int a = n;for (int v=t; v!=s; v = e[p[v]].u) a = min(a, e[p[v]].cap - e[p[v]].flow);for (int v=t; v!=s; v = e[p[v]].u) e[p[v]].flow += a, e[p[v]^1].flow -= a;flow += a; u = s;}bool ok = false;for (int i=cur[u]; i<cnt[u]; ++i) {const edge& ee = e[g[u][i]];if (ee.cap > ee.flow && d[u] == d[ee.v] + 1) {ok = true; p[ee.v] = g[u][i]; cur[u] = i; u = ee.v;break;}}if (!ok) {int m = n1 - 1;for (int i=0; i<cnt[u]; ++i) {const edge& ee = e[g[u][i]];if (ee.cap > ee.flow) m = min(m, d[ee.v]);}if (--num[d[u]] == 0) break;++num[d[u] = m + 1]; cur[u] = 0;if (u != s) u = e[p[u]].u;}}return flow;
}int solve() {int ans = n; char _; memset(cnt, c = 0, sizeof(cnt));for (int i=0; i<n; ++i) add_edge(i, i+n, 1);for (int i=0, u, v; i<m; ++i) cin >> _ >> u >> _ >> v >> _, add_edge(u+n, v, n), add_edge(v+n, u, n);for (int i=0; i<n; ++i) for (int j=i+1; j<n; ++j) ans = min(ans, max_flow(i+n, j));return ans;
}int main() {while (cin >> n >> m) cout << solve() << endl;return 0;
}