题目抽象：给出含有n个点顶点的无向图，给出m条边。求定点联通度 K
算法：将每个顶点v拆成 v' v'' ，v'-->v''的容量为1. 对于原图中的边（u，v） 连边 u''--->v' v''-->u'. 求每对定点的P（u,v）;以u为源点，v为汇点。
我们只需固定一个顶点，枚举其它汇点。
1 #include <iostream>
2 #include <cstdio>
3 #include <cstring>
4 #include <cmath>
5 #include <algorithm>
6 #include <string>
7 #include <vector>
8 #include <set>
9 #include <map>
10 #include <stack>
11 #include <queue>
12 #include <sstream>
13 #include <iomanip>
14 using namespace std;
15 typedef long long LL;
16 const int INF = 0x4fffffff;
17 const double EXP = 1e-5;
18 const int MS = 105;
19 const int SIZE = 100005;
20
21 // 求无向图的顶点连通度 最大流算法
22
23 int cap[MS][MS];
24 int flow[MS][MS]; //将struct c f 拆开成两个数组
25 int que[MS];
26 int pre[MS];
27 int alpha[MS];
28 int qs,qe,nodes;
29 int n,m;
30
31 int max_flow(int source ,int sink)
32 {
33 memset(flow,0,sizeof(flow)); // 0流 开始增加流量
34 int res=0;
35 while(1)
36 {
37 qs=qe=0;
38 que[qe++]=source;
39 memset(pre,-1,sizeof(pre)); // pre可以同时起到flag的作用
40 memset(alpha,-1,sizeof(alpha));
41 alpha[source]=INF;
42 pre[source]=-2; // -2 结束标记，同时又避免了-1,表示未访问
43 while(qs<qe)
44 {
45 int u=que[qs++];
46 for(int v=0;v<nodes;v++)
47 {
48 if(pre[v]==-1&&flow[u][v]<cap[u][v])
49 {
50 que[qe++]=v;
51 pre[v]=u;
52 alpha[v]=min(alpha[u],cap[u][v]-flow[u][v]);
53 }
54 }
55 if(pre[sink]!=-1)
56 {
57 int k=sink;
58 while(pre[k]>=0)
59 {
60 flow[pre[k]][k]+=alpha[sink];
61 flow[k][pre[k]]=-flow[pre[k]][k];
62 k=pre[k];
63 }
64 break;
65 }
66 }
67 if(pre[sink]==-1) //不存在增广路
68 return res;
69 else
70 res+=alpha[sink];
71 }
72 }
73
74 int main()
75 {
76 while(scanf("%d%d",&n,&m)!=EOF)
77 {
78 int a,b,ans=INF;
79 memset(cap,0,sizeof(cap));
80 nodes=2*n;
81 for(int i=0;i<n;i++)
82 cap[i][i+n]=1;
83 for(int i=0;i<m;i++)
84 {
85 scanf(" (%d,%d)",&a,&b);
86 cap[a+n][b]=cap[b+n][a]=INF;
87 }
88 for(int v=1;v<n;v++)
89 {
90 ans=min(ans,max_flow(n,v));
91 }
92 if(ans==INF)
93 ans=n;
94 printf("%d\n",ans);
95 }
96 return 0;
97 }