題目大意:給出一個無向圖,要求刪除盡量少的點,使給定的2點間不再連通,並輸出字典序最小的方案
題型:圖論-網絡流
此題難點在於建圖,後面就是套網絡流的模板.
將點看成邊,例如第i個點可以看成一條有向邊<i*2-1,i*2>,容量為1.
如果j點和i點鄰接,那麼新建2條容量為無窮大的有向邊<i*2,j*2-1>,<j*2,i*2-1>.
然後應用最大流最小割定理,求最大流即為第一問答案.
接著枚舉刪除每一個點i(即刪除有向邊),看最大流是否減少1,如果是則該點在最小割中,然後真的把這一點刪點.
枚舉完每個點之後別忘了將殘量網絡還原.
至於為什麼要這樣建圖, 一時間說不清楚......
Executing...
Test 1: TEST OK [0.008 secs, 3852 KB]
Test 2: TEST OK [0.014 secs, 3852 KB]
Test 3: TEST OK [0.005 secs, 3852 KB]
Test 4: TEST OK [0.022 secs, 3852 KB]
Test 5: TEST OK [0.011 secs, 3852 KB]
Test 6: TEST OK [0.019 secs, 3852 KB]
Test 7: TEST OK [0.019 secs, 3852 KB]
Test 8: TEST OK [0.014 secs, 3852 KB]
Test 9: TEST OK [0.032 secs, 3852 KB]
Test 10: TEST OK [0.046 secs, 3852 KB]
Test 11: TEST OK [0.068 secs, 3852 KB]
All tests OK.
Your program ('telecow') produced all correct answers! This is your
submission #3 for this problem. Congratulations!
1 #include <iostream>
2 #include <cstring>
3 #include <queue>
4 #include <stdio.h>
5 #define msize 210
6 #define INF 1000000000
7 using namespace std;
8
9 int origin[msize][msize]={0};
10 int r[msize][msize]={0}; //殘留網絡，初始為原圖
11 bool visited[msize];
12 int pre[msize];
13 int m,nVertex; //n條邊，m個頂點
14
15 bool bfs(int s,int t) //尋找一條從s到t的增廣路，若找到，返回true
16 {
17 int p;
18 queue<int> Q;
19 memset(pre,-1,sizeof(pre));
20 memset(visited,false,sizeof(visited));
21
22 pre[s]=s;
23 visited[s]=true;
24 Q.push(s);
25
26 while (!Q.empty())
27 {
28 p=Q.front(),Q.pop();
29 for (int i=1; i<=nVertex; i++)
30 {
31 if (r[p][i]>0&&!visited[i])
32 {
33 pre[i]=p;
34 visited[i]=true;
35 if (i==t) return true;
36 Q.push(i);
37 }
38 }
39 }
40
41 return false;
42 }
43
44 int maxFlow(int s,int t)
45 {
46 int flow=0,d;
47
48 while (bfs(s,t))
49 {
50 d=INF;
51 for (int i=t; i!=s; i=pre[i]) d=min(d,r[pre[i]][i]);
52 for (int i=t; i!=s; i=pre[i]) r[pre[i]][i] -= d, r[i][pre[i]] += d;
53 flow += d;
54 }
55 return flow;
56 }
57
58 int main()
59 {
60 freopen("telecow.in","r",stdin);
61 freopen("telecow.out","w",stdout);
62 int s,e,c;
63
64 cin>>nVertex>>m>>s>>e;
65 nVertex*=2;
66 for(int i=0;i<m;i++)
67 {
68 int a,b;
69 scanf("%d%d",&a,&b);
70 r[a*2-1][a*2]=1;
71 r[b*2-1][b*2]=1;
72 r[a*2][b*2-1]=INF;
73 r[b*2][a*2-1]=INF;
74 }
75 memcpy(origin,r,sizeof r);
76 int maxflow=maxFlow(s*2,e*2-1);
77 int sum=maxflow;
78 memcpy(r,origin,sizeof r);
79 printf("%d\n",maxflow);
80
81 bool first=true;
82 int cnt=0;
83 for(int i=1;i<=nVertex/2;i++) // 模擬刪掉第i個點
84 {
85 if(i==s || i==e)
86 continue;
87 if(cnt==sum)
88 {
89 break;
90 }
91 memcpy(origin,r,sizeof r);
92 r[i*2-1][i*2]=0;
93
94 if(maxFlow(s*2,e*2-1)+1==maxflow)
95 {
96 maxflow--;
97 cnt++;
98 if(first)
99 {
100 first=false;
101 }
102 else
103 {
104 printf(" ");
105 }
106 printf("%d",i);
107 memcpy(r,origin,sizeof r);
108 r[i*2-1][i*2]=0;
109 }
110 else
111 {
112 memcpy(r,origin,sizeof r);
113 }
114 }
115 cout<<endl;
116 return 0;
117 }
