题目链接
https://vjudge.net/problem/UVA-10480
题意
无向图求最小割的方案
思路
最小割部分是模版,问题在于最小割的方案如何输出。
首先根据最小割最大流定理,我们跑一遍Dinic就可以求出最小割,这时残量网络中s和t已经不再联通了。我们可以从s开始跑一遍dfs,沿着所有还未满流的边搜索,所有能到达的节点就是和s在同一集合的节点。之后我们遍历每一条边,将边起点终点不在同一集合内的输出即可。
注意需要修改下链式前向星,每一个edge结构体内存一下起点。
附一篇最小割相关拓展的优质博客:https://www.cnblogs.com/lyttt/p/11817977.html
代码
#include<cstdio> #include<iostream> #include<iomanip> #include<map> #include<string> #include<queue> #include<cstring> #include<algorithm> #include<cmath> #include<cstdlib> #define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); #define endl "\n" //#define int long long using namespace std; typedef long long ll; const int inf=0x3f3f3f3f; const int maxn=1010; const int maxe=1010; int head[maxn],cnt; struct Edge{
int u; int v; int w; int next; }edge[maxe]; int n,m,s,t; ll maxflow; int deep[maxn]; int now[maxe]; bool s_or_t[maxn];//0代表和t相连,1是和s相连 void init(){
memset(head,-1,sizeof(head)); memset(s_or_t,0,sizeof s_or_t); cnt=0; maxflow=0; return ; } void add(int u,int v,int w){
// cout<<u<<" "<<v<<" "<<w<<endl; edge[cnt].u=u; edge[cnt].v=v; edge[cnt].w=w; edge[cnt].next=head[u]; head[u]=cnt++; } inline bool bfs(){
memset(deep,0x3f,sizeof(deep)); queue<int>q; q.push(s);deep[s] = 0;now[s] = head[s]; while(q.size()){
int x = q.front();q.pop(); for(int i=head[x];i!=-1;i=edge[i].next){
int y=edge[i].v; if(edge[i].w>0&&deep[y]==inf){
q.push(y); now[y]=head[y]; deep[y]=deep[x]+1; if(y==t) return 1; } } } return 0; } ll dfs(int x,int flow){
if(x==t) return flow; ll ans = 0,k,i; for(i=now[x];i!=-1&&flow;i=edge[i].next){
now[x]=i; int y=edge[i].v; if(edge[i].w>0&&(deep[y]==deep[x]+1)){
k=dfs(y,min(flow,edge[i].w)); if(!k) deep[y]=inf; edge[i].w-=k; edge[i^1].w+=k; ans+=k; flow-=k; } } return ans; } void dinic(){
while(bfs()) maxflow+=dfs(s,inf); } //在残量网络中跑dfs void output_dfs(int u){
if(s_or_t[u]) return ; else{
s_or_t[u]=1; } for(int i=head[u];~i;i=edge[i].next) if(edge[i].w>0)//只能通过还有余量的边 output_dfs(edge[i].v); } int main(){
IOS while(cin>>n>>m){
if(!n&&!m) break; init(); while(m--){
int u,v,w; cin>>u>>v>>w; add(u,v,w); add(v,u,w); } s=1,t=2; dinic(); output_dfs(s); for(int i=0;i<cnt;i+=2){
int u=edge[i].u,v=edge[i].v; if(s_or_t[u]!=s_or_t[v]) cout<<u<<" "<<v<<endl; } cout<<endl; } return 0; }
讯享网

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容,请联系我们,一经查实,本站将立刻删除。
如需转载请保留出处:https://51itzy.com/kjqy/131879.html