Uva1660 (点联通度、边联通度问题)

题意：

给定一个n（n<=50）的无向图，问最小删去几个点，可以使得这个图不连通

解法：

1. 基本概念

(1)一个具有 N 个顶点的图，在去掉任意 K-1 个顶点后 (1<=K<=N) 所得的子图仍连通，而去掉 K 个顶点后的图不连通则称 G 是连通的，那么K 称作图 G 的点连通度

(2)相应地如果至少去掉 K 条边使这个图不连通，则 K 成为图的边连通度

2. 求解思路

对于求解边联通度的问题，为每条边赋权值为1，然后求确定一点作为源点，枚举此点外的每个点作为汇点求最大流。
点联通度问题可以转换到边联通度问题上来，具体转换方法如下
- 若 G 为无向图，假设有n个点：
  
      (1) 原 G 图中的每个顶点 v 变成两个顶点 v' 和 v+n ，顶点 v 至 v+n 有一条弧（有向边）连接，弧容量为 1;
  
      (2) 原 G 图中的每条边  e ＝ uv ，连一条 u+n 到 v 的弧，再连一条 v+n 到 u 的弧，容量均为INF
  
      (3) A” 为源顶点， B' 为汇顶点
  
       注意：弧是有向边
- 若 G 为有向图，假设有n个点：
  
      (1) 原 G 图中的每个顶点 v 变成两个顶点 v' 和 v+n ，顶点 v 至 v+n 有一条弧（有向边）连接，弧容量为 1;
  
      (2) 原 G 图中的每条弧  e ＝ uv 变成一条有向轨 u'u"v'v" ，其中轨上的弧 u"v' 的容量为 ∞;
  
      (3) A” 为源顶点， B' 为汇顶点
指定一个源点 A" ，枚举汇点B'，求 A" 到 B' 的最大流 F

  1 #include<bits/stdc++.h>
  2 #define REP(i, a, b) for(int i = (a); i < (b); i++)
  3 #define MEM(a,x) memset(a,x,sizeof(a)) 
  4 #define INF 0x3f3f3f3f 
  5 #define MAXN 300+10
  6 using namespace std;
  7 struct Edge {
  8     int from, to, cap, flow;
  9 };
 10 struct Dinic {
 11     int n, m, s, t;
 12     vector<Edge>edges;
 13     vector<int>G[MAXN];
 14     bool vis[MAXN];
 15     int d[MAXN];
 16     int cur[MAXN];
 17     void init() {
 18         for (int i = 0; i < MAXN; i++) G[i].clear();
 19         edges.clear(); 
 20         memset(d, 0, sizeof(d));
 21     }
 22     void AddEdge(int from, int to, int cap) {
 23         edges.push_back({ from, to, cap, 0 });
 24         edges.push_back({ to, from, 0, 0 });
 25         m = edges.size();
 26         G[from].push_back(m - 2);
 27         G[to].push_back(m - 1);
 28     }
 29     bool BFS() {
 30         int x, i;
 31         memset(vis, 0, sizeof(vis));
 32         queue<int>Q;
 33         Q.push(s);
 34         d[s] = 0;
 35         vis[s] = 1;
 36         while (!Q.empty()) {
 37             x = Q.front(), Q.pop();
 38             for (i = 0; i < G[x].size(); i++) {
 39                 Edge & e = edges[G[x][i]];
 40                 if (!vis[e.to] && e.cap > e.flow) {
 41                     vis[e.to] = 1;
 42                     d[e.to] = d[x] + 1;
 43                     Q.push(e.to);
 44                 }
 45             }
 46         }
 47         return vis[t];
 48     }
 49     int DFS(int x, int a) {
 50         if (x == t || a == 0)
 51             return a;
 52         int flow = 0, f;
 53         for (int &i = cur[x]; i < G[x].size(); i++) {
 54             Edge & e = edges[G[x][i]];
 55             if (d[x] + 1 == d[e.to] && (f = DFS(e.to, min(a, e.cap - e.flow))) > 0) {
 56                 e.flow += f;
 57                 edges[G[x][i] ^ 1].flow -= f;
 58                 flow += f;
 59                 a -= f;
 60                 if (a == 0)
 61                     break;
 62             }
 63         }
 64         return flow;
 65     }
 66     int Maxflow(int s, int t) {
 67         this->s = s, this->t = t;
 68         int flow = 0;
 69         while (BFS()) {
 70             memset(cur, 0, sizeof(cur));
 71             flow += DFS(s, INF);
 72         }
 73         return flow;
 74     }
 75 }Men;
 76 int c[100][100];
 77 int main() {
 78     int n, m;
 79     while (scanf("%d%d", &n, &m) != EOF) {
 80         if (n == 0) { puts("0"); continue; }
 81         else if (n == 1) { puts("1"); continue; }
 82         else if (m == 0) { puts("0"); continue; }
 83         Men.init();
 84         int u, v, uu, vv;
 85         MEM(c, 0);
 86         REP(i, 0, n) Men.AddEdge(i, i + n, 1);    
 87         REP(i, 0, m) {
 88             scanf(" (%d,%d)", &u, &v);
 89             uu = u + n; vv = v + n;
 90             Men.AddEdge(uu, v, INF); Men.AddEdge(vv, u, INF);
 91         }
 92         int ans = INF;
 93         vector<Edge>o=Men.edges;
 94         REP(i, 1, n) {
 95             Men.edges = o;
 96             ans = min(ans, Men.Maxflow(n, i));
 97         }
 98         printf("%d
", ans == INF ? n: ans);
 99     }
100     return 0;
101 }