求最小點(diǎn)集，可以通過(guò)最小割集轉(zhuǎn)化，把點(diǎn)拆開(kāi)變成邊，這樣就轉(zhuǎn)化成了求最小割集；
注意把點(diǎn)拆開(kāi)時(shí)邊的轉(zhuǎn)變：把每個(gè)點(diǎn)i拆成兩個(gè)點(diǎn)i1,i2，這兩個(gè)點(diǎn)之間建立一條邊權(quán)為1的有向弧。對(duì)于原圖中邊(i,j)，建立(i2,j1)和(j2,i1)兩條邊權(quán)為∞的有向弧。對(duì)于每個(gè)點(diǎn)i（非c1,c2），把邊(i1,i2)去掉，求最大流，記為nowflow，記當(dāng)前找到的最小割集中元素的數(shù)量為cnt。如果
netflow-cnt=nowflow+1，那么點(diǎn)i一定是最小割集中的割點(diǎn)，記錄下來(lái)。否則將邊(i1,i2)重新加上。直到
cnt=netflow，當(dāng)前找的集合就是最小割集。
1 #include<iostream>
2 using namespace std;
3 int n,m,s,t;
4 int graph[101*2][101*2];//殘留網(wǎng)絡(luò)
5 int cp[101*2][202];
6 int Edmonds_Karp(int s,int t)
7 {
8 int flow=0;
9 int cp[101*2];
10 int pre[101*2];
11 int que[100000];
12 while(true)
13 {
14 cp[s]=INT_MAX;
15 memset(pre,0,sizeof(pre));
16 int head=0,tail=1;que[0]=s;
17 while(head!=tail)
18 {
19 int i=que[head++];
20 for(int j=1;j<=2*n;j++) //節(jié)點(diǎn)從0算起
21 if(j != i && !pre[j] && graph[i][j]>0)
22 {
23 cp[j]=min(cp[i],graph[i][j]);
24 que[tail++]=j;
25 pre[j]=i;
26 }
27 }
28 if(pre[t]==0)break;
29 int i=t;
30 while(i!=s)
31 {
32 int j=pre[i];
33 graph[j][i]-=cp[t];
34 graph[i][j]+=cp[t];
35 i=j;
36 }
37 flow+=cp[t];
38 }
39 return flow;
40 }
41 int main()
42 {
43 int a,b;
44 freopen("telecow.in","r",stdin);
45 freopen("telecow.out","w",stdout);
46 scanf("%d%d%d%d",&n,&m,&s,&t);
47 for(int i=1;i<=n;++i)
48 graph[2*i-1][2*i]=1;
49 for(int i=1;i<=m;++i)
50 {
51 scanf("%d%d",&a,&b);
52 graph[2*b][2*a-1]=graph[2*a][2*b-1]=INT_MAX;
53 }
54 for(int i=1;i<=n;++i)
55 graph[2*t][2*i-1]=graph[2*i][s*2-1]=0;
56 memcpy(cp,graph,sizeof(graph));
57 int Max;
58 printf("%d\n",Max=Edmonds_Karp(2*s,2*t-1));
59 bool flag=1;
60 for(int i=1;i<=n;++i)
61 {
62 if(i==s||i==t)continue;
63 memcpy(graph,cp,sizeof(cp));
64 graph[2*i-1][2*i]=0;
65 int tmp=Edmonds_Karp(2*s,2*t-1);
66 cp[2*i-1][2*i]=1;
67 if(tmp+1==Max)
68 {
69 if(flag)
70 {
71 printf("%d",i);
72 flag=0;
73 }
74 else printf(" %d",i);
75 cp[2*i-1][2*i]=0;
76 Max=tmp;
77 }
78 }
79 printf("\n");
80 return 0;
81 }
82