首页 > 代码库 > POJ 1815 Friendship（最小割+字典序输出割点）
POJ 1815 Friendship（最小割+字典序输出割点）
http://poj.org/problem?id=1815
题意：
在现代社会，每个人都有自己的朋友。由于每个人都很忙，他们只通过电话联系。你可以假定A可以和B保持联系，当且仅当：①A知道B的电话号码；②A知道C的电话号码，而C能联系上B。如果A知道B的电话号码，则B也知道A的电话号码。
思路：
这题是要我们删点，既然是删点，那么就要拆点，容量就是1。
接下来凡是能联系的，就连边，容量为INF，因为我们不是要删除这些边。跑遍最大流就能算出至少要删除多少个点。
这道题的关键是要字典序顺序输出最小割的点集，在跑一遍最大流之后，我们按字典序顺序依次枚举每个点，将该点删除后然后再去跑最大流，如果流量减少了，说明它是割点。
1 #include<iostream> 2 #include<algorithm> 3 #include<cstring> 4 #include<cstdio> 5 #include<sstream> 6 #include<vector> 7 #include<stack> 8 #include<queue> 9 #include<cmath> 10 #include<map> 11 #include<set> 12 using namespace std; 13 typedef long long ll; 14 typedef pair<int,int> pll; 15 const int INF = 0x3f3f3f3f; 16 const int maxn = 20000 + 5; 17 18 struct Edge 19 { 20 int from,to,cap,flow; 21 Edge(int u,int v,int w,int f):from(u),to(v),cap(w),flow(f){} 22 }; 23 24 struct Dinic 25 { 26 int n,m,s,t; 27 vector<Edge> edges; 28 vector<int> G[maxn]; 29 bool vis[maxn]; 30 int cur[maxn]; 31 int d[maxn]; 32 33 void init(int n) 34 { 35 this->n=n; 36 for(int i=0;i<n;++i) G[i].clear(); 37 edges.clear(); 38 } 39 40 void AddEdge(int from,int to,int cap) 41 { 42 edges.push_back( Edge(from,to,cap,0) ); 43 edges.push_back( Edge(to,from,0,0) ); 44 m=edges.size(); 45 G[from].push_back(m-2); 46 G[to].push_back(m-1); 47 } 48 49 bool BFS() 50 { 51 queue<int> Q; 52 memset(vis,0,sizeof(vis)); 53 vis[s]=true; 54 d[s]=0; 55 Q.push(s); 56 while(!Q.empty()) 57 { 58 int x=Q.front(); Q.pop(); 59 for(int i=0;i<G[x].size();++i) 60 { 61 Edge& e=edges[G[x][i]]; 62 if(!vis[e.to] && e.cap>e.flow) 63 { 64 vis[e.to]=true; 65 d[e.to]=d[x]+1; 66 Q.push(e.to); 67 } 68 } 69 } 70 return vis[t]; 71 } 72 73 int DFS(int x,int a) 74 { 75 if(x==t || a==0) return a; 76 int flow=0, f; 77 for(int &i=cur[x];i<G[x].size();++i) 78 { 79 Edge &e=edges[G[x][i]]; 80 if(d[e.to]==d[x]+1 && (f=DFS(e.to,min(a,e.cap-e.flow) ) )>0) 81 { 82 e.flow +=f; 83 edges[G[x][i]^1].flow -=f; 84 flow +=f; 85 a -=f; 86 if(a==0) break; 87 } 88 } 89 return flow; 90 } 91 92 int Maxflow(int s,int t) 93 { 94 this->s=s; this->t=t; 95 int flow=0; 96 while(BFS()) 97 { 98 memset(cur,0,sizeof(cur)); 99 flow +=DFS(s,INF);100 }101 return flow;102 }103 }DC;104 105 int n,s,t;106 int mp[maxn][maxn];107 108 int main()109 {110 //freopen("in.txt","r",stdin);111 while(~scanf("%d%d%d",&n,&s,&t))112 {113 int dst=2*n+1;114 DC.init(dst+1);115 116 for(int i=1;i<=n;i++)117 {118 if(i==s || i==t) DC.AddEdge(i,i+n,INF);119 else DC.AddEdge(i,i+n,1);120 }121 122 for(int i=1;i<=n;i++)123 {124 for(int j=1;j<=n;j++)125 {126 scanf("%d",&mp[i][j]);127 if(i==j) continue;128 if(mp[i][j]) DC.AddEdge(i+n,j,INF);129 }130 }131 132 if(mp[s][t]) {puts("NO ANSWER!");continue;}133 134 int cnt=DC.Maxflow(s,t);135 vector<int> ans;136 137 printf("%d\n",cnt);138 if(cnt==0) continue;139 140 for(int i=0;i<2*n;i+=2) //前2*n条边为每个顶点，依次枚举141 {142 Edge& e=DC.edges[i];143 if(e.from==s || e.from==t) continue;144 e.cap=0; //删边145 for(int j=0;j<2*n;j++) DC.edges[j].flow = 0;146 int tmp=DC.Maxflow(s,t); //如果流量改变，说明这条边是割边147 if(tmp<cnt)148 {149 cnt=tmp;150 ans.push_back(e.from);151 }152 else e.cap=1;153 if(cnt<=0) break;154 }155 for(int i=0;i<ans.size();i++)156 {157 printf("%d%c",ans[i],i==ans.size()-1?‘\n‘:‘ ‘);158 }159 printf("\n");160 }161 return 0;162 }
POJ 1815 Friendship（最小割+字典序输出割点）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。