首页 > 代码库 > zoj2587唯一最小割
zoj2587唯一最小割
从源点开始遍历,从汇点开始遍历,如果遍历了所有的点则最小割唯一,否则不唯一。
#include <cstdio>#include <cstdlib>#include <cstring>#include <algorithm>#include <cmath>#include <stack>#include <queue>#include <vector>#include <map>#include <string>#include <iostream>using namespace std;int n;int s;int e1;const int maxn=1111;int level[maxn];int Min(int a,int b){ return a>b?b:a;}const int INF=0xfffffff;struct edge{ int op; int to;int next;int val;}e[222222];int len;int head[maxn];void add(int from,int to,int val){ e[len].to=to;e[len].val=val;e[len].next=head[from]; e[len].op=len+1; head[from]=len++; e[len].to=from;e[len].val=0;e[len].next=head[to]; head[to]=len++;}bool bfs(){ int q[maxn*2];int l=0;int r=0; memset(level,0,sizeof(level)); level[s]=1; q[r++]=s; while(l<r){ int cur=q[l++]; for(int i=head[cur];i!=-1;i=e[i].next){ int cc=e[i].to; if(e[i].val&&!level[cc]){ q[r++]=cc; level[cc]=level[cur]+1; } } } return level[e1];}int dfs(int x,int val){ int sum=0;if(x==e1) return val; for(int i=head[x];i!=-1&&val;i=e[i].next){ int cc=e[i].to; if(level[cc]==level[x]+1&&e[i].val){ int t=dfs(cc,Min(val,e[i].val)); e[i].val-=t;e[e[i].op].val+=t; sum+=t;val-=t; } } if(sum==0) level[x]=-1; return sum;}int dinic(){ int ans=0;int t; while(bfs()){ while(t=dfs(s,INF)) ans+=t; } return ans;}void judge(){ int vis[maxn]; memset(vis,0,sizeof(vis)); int q[maxn*2];int l=0;int r=0; q[r++]=s; while(l<r){ int cur=q[l++]; for(int i=head[cur];i!=-1;i=e[i].next){ int cc=e[i].to; if(e[i].val&&!vis[cc]){ vis[cc]=1;q[r++]=cc; } } } l=0;r=0; q[r++]=e1; while(l<r){ int cur=q[l++]; for(int i=head[cur];i!=-1;i=e[i].next){ int cc=e[i].to; if(e[i^2].val&&!vis[cc]){ vis[cc]=1;q[r++]=cc; } } } int ans=0; vis[s]=1;vis[e1]=1; for(int i=1;i<=n;i++) if(!vis[i]) ans++; if(!ans) printf("UNIQUE\n"); else printf("AMBIGUOUS\n");}int main(){ int m,a,b; while(scanf("%d%d%d%d",&n,&m,&a,&b),n||m||a||b){ len=0;memset(head,-1,sizeof(head)); s=a;e1=b; for(int i=0;i<m;i++){ int l;int r;int val; scanf("%d%d%d",&l,&r,&val); add(l,r,val); add(r,l,val); } int k=dinic(); judge(); } return 0;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。