首页 > 代码库 > 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;}