[ZOJ 2587] 求最小割是否唯一、网络流**

【题目大意】给定一个有源汇的无向连通图，问你这个流网络的最小割是否唯一。

【算法分析】直接最小割，然后分别从S和T出发，沿着残余网络dfs，如果能遍历所有点，那么则该最小割是唯一的，否则那些不能遍历的点就是夹在两个方案中间的点。

【其它】1RE，1A
RE原因：好像数组没开够，但是按照计算应该是够了。。。反正开大了一倍就AC了。
2084877 2010-01-31 21:51:22 Accepted 2587 C++ 440 2156 edward
【CODE】
#include #include #include #define N 1000
#define E 100000
struct gtp{int x,y,next,op,c;}g[E];
int n,e,m,ls[N],fa[N],cur[N],d[N],num[N],S,T,v1[N],v2[N];

void addedge(int x,int y,int c){
e++;
g[e].x=x; g[e].y=y; g[e].c=c; g[e].op=e+1; g[e].next=ls[x]; ls[x]=e;
e++;
g[e].x=y; g[e].y=x; g[e].c=0; g[e].op=e-1; g[e].next=ls[y]; ls[y]=e;
}   

void init(){
e=0; memset(ls,0,sizeof(ls));
for (int i=1;i<=m;i++){
int x,y,c;
scanf("%d%d%d",&x,&y,&c);
addedge(x,y,c);
addedge(y,x,c);
}   
}   

void relabel(int k){
int mm=n;
cur[k]=ls[k];
for (int t=ls[k];t;t=g[t].next)
if (g[t].c && d[g[t].y]d[k]=mm+1;
}   

void change(){
int nf=0x7FFFFFFF;
for (int i=T;i!=S;i=g[fa[i]].x)
if (g[fa[i]].cfor (int i=T;i!=S;i=g[fa[i]].x){
g[fa[i]].c-=nf;
g[g[fa[i]].op].c+=nf;
}   
}   

void sap(){
memset(d,0,sizeof(d));
memset(num,0,sizeof(num));
for (int i=1;i<=n;i++) cur[i]=ls[i];
num[0]=n;
int i=S;
while (d[S]for (;cur[i];cur[i]=g[cur[i]].next)
if (g[cur[i]].c && d[g[cur[i]].y]+1==d[i]) break;
if (!cur[i]){
if (!–num[d[i]]) break;
relabel(i);
num[d[i]]++;
if (i!=S) i=g[fa[i]].x;
}   
else{
fa[g[cur[i]].y]=cur[i];
i=g[cur[i]].y;
if (i==T){
change();
i=S;
}   
}   
}   
}   

void dfs1(int k){
v1[k]=1;
for (int t=ls[k];t!=0;t=g[t].next)
if (g[t].c && !v1[g[t].y]) dfs1(g[t].y);
}   

void dfs2(int k){
v2[k]=1;
for (int t=ls[k];t!=0;t=g[t].next)
if (g[t].c && !v2[g[t].y]) dfs2(g[t].y);
}   

void changegraph(){
memset(ls,0,sizeof(ls));
for (int i=1;i<=e;i++){
int tmp=g[i].x; g[i].x=g[i].y; g[i].y=tmp;
g[i].next=ls[g[i].x];
ls[g[i].x]=i;
}   
}   

bool flag(){
memset(v1,0,sizeof(v1));
memset(v2,0,sizeof(v2));
dfs1(S);
changegraph();
dfs2(T);
for (int i=1;i<=n;i++)
if (!v1[i] && !v2[i]) return false;
return true;
}   

int main(){
for (;;){
scanf("%d%d%d%d",&n,&m,&S,&T);
if (n+m+S+T==0) break;
init();
sap();
if (flag()) printf("UNIQUEn");
else printf("AMBIGUOUSn");
}   
}