poj 1966(无向图点连通度 )

无向图点连通度：

构造有向图，再枚举源汇点求最小割。

1、无向图中任一个点u拆边为u和u+N，连容量为1的有向边。

2、对于无向图中原有的任意无向边(u,v)，在构造的有向图中添加边(u+N,v)和(v+N,v)，容量均为无穷。（拆边规则）

3、O(n^2)枚举源点(拆后出点)、汇点(拆后入点)求最小割的最小值(注意源点与汇点直接相连的情况，显然此时最大流流出来的是inf)。

View Code

  1 // File Name: 1966.cpp
  2 // Author: Missa
  3 // Created Time: 2013/4/19 星期五 10:29:17
  4 
  5 #include<iostream>
  6 #include<cstdio>
  7 #include<cstring>
  8 #include<algorithm>
  9 #include<cmath>
 10 #include<queue>
 11 #include<stack>
 12 #include<string>
 13 #include<vector>
 14 #include<cstdlib>
 15 #include<map>
 16 #include<set>
 17 using namespace std;
 18 #define CL(x,v) memset(x,v,sizeof(x));
 19 #define R(i,st,en) for(int i=st;i<en;++i)
 20 #define LL long long
 21 
 22 const int inf = 0x3f3f3f3f;
 23 const int maxn = 105;
 24 const int maxm = 10010;
 25 struct Edge
 26 {
 27     int v, c, next;//指向点,流量,下一个点
 28 }p[maxm << 1];
 29 int head[maxn], e;
 30 int d[maxn], cur[maxn];//层次记录，当前弧优化
 31 int n, m, st, en;
 32 void init()
 33 {
 34     e = 0;
 35     memset(head, -1, sizeof(head));
 36 }
 37 void addEdge(int u, int v, int c)
 38 {
 39     p[e].v = v; p[e].c = c; 
 40     p[e].next = head[u];head[u] = e++;
 41     p[e].v = u; p[e].c = 0; //无向图时逆边赋值流量cap，有向图时赋值0.
 42     p[e].next = head[v];head[v] = e++;
 43 }
 44 int bfs(int st, int en)
 45 {
 46     queue <int> q;
 47     memset(d, 0, sizeof(d));
 48     d[st] = 1;
 49     q.push(st);
 50     while (!q.empty())
 51     {
 52         int u = q.front(); q.pop();
 53         for (int i = head[u]; i != -1; i = p[i].next)
 54         {
 55             if (p[i].c > 0 && !d[p[i].v])
 56             {
 57                 d[p[i].v] = d[u] + 1;
 58                 q.push(p[i].v);
 59             }
 60         }
 61     }
 62     return d[en];
 63 }
 64 int dfs(int u, int a)//a表示流量
 65 {
 66     if (u == en || a == 0) return a;
 67     int f, flow = 0;
 68     for (int& i = cur[u]; i != -1; i = p[i].next)
 69     {
 70         if (d[u] + 1 == d[p[i].v] && (f = dfs(p[i].v,min(a,p[i].c))) > 0)
 71         {
 72             p[i].c -= f;
 73             p[i^1].c += f;
 74             flow += f;
 75             a -= f;
 76             if (!a) break;
 77         }
 78     }
 79     return flow;
 80 }
 81 int dinic(int st, int en, int tmp)
 82 {
 83     int res = 0;
 84     while (bfs(st, en))
 85     {
 86         for (int i = 0; i <= n; ++i)
 87             cur[i] = head[i];
 88         res += dfs(st, inf);
 89         if (res > tmp) return res;
 90     }
 91     return res;
 92 }
 93 int N;
 94 struct Node
 95 {
 96     int u, v;
 97 }edg[maxm];
 98 void build(int u, int v)
 99 {
100     init();
101     n = N << 1;
102     st = u + N, en = v;
103     for (int i = 1; i <= N; ++i)
104         addEdge(i, i +N, 1);
105     for (int i = 0; i < m; ++i)
106     {
107         addEdge(edg[i].u + N, edg[i].v, inf);
108         addEdge(edg[i].v + N, edg[i].u, inf);
109     }
110 }
111 
112 int main()
113 {
114     while(~scanf("%d%d",&N,&m))
115     {
116         for (int i = 0; i < m; ++i)
117         {
118             scanf(" (%d,%d)", &edg[i].u, &edg[i].v);
119             edg[i].u++;
120             edg[i].v++;
121         }
122         int ans = inf;
123         for (int i = 1; i <= N; ++i)
124             for (int j = 1; j <= N; ++j)
125             {
126                 if ( i == j) continue;
127                 build(i, j);
128                 int tmp = dinic(st, en, ans);
129                 if ( tmp < ans)
130                     ans = tmp;
131             }
132         if (ans == inf) ans = N;
133         printf("%d\n",ans);
134     }
135     return 0;
136 }