ZOJ 2587 Unique Attack은 최소 베기가 유일한지 여부를 판단합니다.

Unique Attack
Time Limit: 5 Seconds
Memory Limit: 32768 KB
N supercomputers in the United States of Antarctica are connected into a network. A network has a simple topology: M different pairs of supercomputers are connected to each other by an optical fibre. All connections are two-way, that is, they can be used in both directions. Data can be transmitted from one computer to another either directly by a fibre, or using some intermediate computers.
A group of terrorists is planning to attack the network. Their goal is to separate two main computers of the network, so that there is no way to transmit data from one of them to another. For each fibre the terrorists have calculated the sum of money they need to destroy the fibre. Of course, they want to minimize the cost of the operation, so it is required that the total sum spent for destroying the fibres was minimal possible.
Now the leaders of the group wonder whether there is only one way to do the selected operation. That is, they want to know if there are no two different sets of fibre connections that can be destroyed, such that the main supercomputers cannot connect to each other after it and the cost of the operation is minimal possible.
Input
The input file consists of several cases. In each case, the first line of the input file contains N, M, A and B (2 <= N <= 800, 1 <= M <= 10000, 1 <= A,B <= N, A != B), specifying the number of supercomputers in the network, the number of fibre connections, and the numbers of the main supercomputers respectively. A case with 4 zeros indicates the end of file.
Next M lines describe fibre connections. For each connection the numbers of the computers it connects are given and the cost of destroying this connection. It is guaranteed that all costs are non-negative integer numbers not exceeding 105, no two computers are directly connected by more than one fibre, no fibre connects a computer to itself and initially there is the way to transmit data from one main supercomputer to another.
Output
If there is only one way to perform the operation, output "UNIQUE"in a single line. In the other case output "AMBIGUOUS".
Sample Input
4 4 1 2 1 2 1 2 4 2 1 3 2 3 4 1 4 4 1 2 1 2 1 2 4 1 1 3 2 3 4 1 0 0 0 0
Sample Output
UNIQUE AMBIGUOUS
Author: Andrew Stankevich Source: Andrew Stankevich's Contest #5
해법 1:
한 번의 최대 흐름을 구하고 모든 절단에 대해 그 권한을 inf로 바꾸고 다시 한 번의 최대 흐름을 한다. 만약에 최초의 흐름 값과 같다면 최소 절단이 유일하지 않다는 것을 의미한다.
사용 시 1150ms
 
해법 2:
먼저 최대 흐름을 한 번 하고 최대 흐름을 한 다음에 그림은 두 부분으로 나누어 각각 원점과 환점에서 dfs를 진행한다.
도처에 표시된 점, 그림에서 찾을 수 없는 점이 있는지 없는지, 모두 찾을 수 있는 점은 가장 작게 자르는 것이 유일하다.
 
사고방식(전): 최소 베어링이 유일한지 판단하고 한 번의 최대 흐름을 구한 다음에 잔류 네트워크에서 각각 원환에서 dfs를 시작하여 최소 베어링[S,T]을 찾아낸다. 만약에 SUT가 모든 점을 포함하지 않는다면 최소 베어링이 유일하지 않다.가설점 i가 SUT에 포함되지 않으면 잔류 네트워크에서 s가 i에 도달할 수 없고 i가 t에 도달할 수 없다. 즉, i에 들어간 변과 i에서 나간 변이 모두 만류한다. 만약에 어떤 변이 i에 들어간 변 x가 만류한다고 가정하면 이런 유량은 몇 개의 변 y에서 i로 유출된다. 만약에 x를 가장자리로 선택하거나 대응하는 y를 가장자리로 선택하면 최대 흐름에 영향을 주지 않는다. 즉, 최소 절단 용량이 변하지 않고 최소 절단도 유일하지 않다.
사용 시간 130ms
 
코드 1:

#include<cstdio>
#include<cstring>
#define N 1005
#define M 20005
#define inf 999999999
#define min(a,b) ((a)<(b)?(a):(b))

int n,m,s,t,num,adj[N],dis[N],q[N],f[N],f1[N];
struct edge
{
	int v,w,c,pre;
}e[M];
void insert(int u,int v,int w)
{
	e[num]=(edge){v,w,w,adj[u]};
	adj[u]=num++;
	e[num]=(edge){u,w,w,adj[v]};
	adj[v]=num++;
}
int bfs()
{
	int i,x,v,head=0,tail=0;
	memset(dis,0,sizeof(dis));
	dis[s]=1;
	q[tail++]=s;
	while(head<tail)
	{
		x=q[head++];
		for(i=adj[x];~i;i=e[i].pre)
			if(e[i].w&&!dis[v=e[i].v])
			{
				dis[v]=dis[x]+1;
				if(v==t)
					return 1;
				q[tail++]=v;
			}
	}
	return 0;
}
int dfs(int x,int limit)
{
	if(x==t)
		return limit;
	int i,v,tmp,cost=0;
	for(i=adj[x];~i&&cost<limit;i=e[i].pre)
		if(e[i].w&&dis[x]==dis[v=e[i].v]-1)
		{
			tmp=dfs(v,min(limit-cost,e[i].w));
			if(tmp)
			{
				e[i].w-=tmp;
				e[i^1].w+=tmp;
				cost+=tmp;
			}
			else
				dis[v]=-1;
		}
	return cost;
}
int Dinic()
{
	int ans=0;
	while(bfs())
		ans+=dfs(s,inf);
	return ans;
}
int cnt1,cnt2;
void dfs1(int x)
{
	f[x]=1;
	cnt1++;
	for(int i=adj[x];~i;i=e[i].pre)
		if(!f[e[i].v]&&e[i].w)
			dfs1(e[i].v);
}
void dfs2(int x)
{
	f1[x]=1;
	cnt2++;
	for(int i=adj[x];~i;i=e[i].pre)
		if(!f1[e[i].v]&&e[i^1].w)
			dfs2(e[i].v);
}
int main()
{
	while(~scanf("%d%d%d%d",&n,&m,&s,&t),n)
	{
		int i,j,k;
		num=0;
		memset(adj,-1,sizeof(adj));
		while(m--)
		{
			scanf("%d%d%d",&i,&j,&k);
			insert(i,j,k);
		}
		Dinic();
		memset(f,0,sizeof(f));
		memset(f1,0,sizeof(f1));
		cnt1=cnt2=0;
		dfs1(s);
		dfs2(t);
		puts(cnt1+cnt2==n?"UNIQUE":"AMBIGUOUS");
	}
}

 
코드 2:

#include<cstdio>
#include<cstring>
#define N 1005
#define M 20005
#define inf 999999999
#define min(a,b) ((a)<(b)?(a):(b))

int n,m,s,t,num,adj[N],dis[N],q[N],f[N],f1[N];
struct edge
{
	int v,w,c,pre;
}e[M];
void insert(int u,int v,int w)
{
	e[num]=(edge){v,w,w,adj[u]};
	adj[u]=num++;
	e[num]=(edge){u,w,w,adj[v]};
	adj[v]=num++;
}
int bfs()
{
	int i,x,v,head=0,tail=0;
	memset(dis,0,sizeof(dis));
	dis[s]=1;
	q[tail++]=s;
	while(head<tail)
	{
		x=q[head++];
		for(i=adj[x];~i;i=e[i].pre)
			if(e[i].w&&!dis[v=e[i].v])
			{
				dis[v]=dis[x]+1;
				if(v==t)
					return 1;
				q[tail++]=v;
			}
	}
	return 0;
}
int dfs(int x,int limit)
{
	if(x==t)
		return limit;
	int i,v,tmp,cost=0;
	for(i=adj[x];~i&&cost<limit;i=e[i].pre)
		if(e[i].w&&dis[x]==dis[v=e[i].v]-1)
		{
			tmp=dfs(v,min(limit-cost,e[i].w));
			if(tmp)
			{
				e[i].w-=tmp;
				e[i^1].w+=tmp;
				cost+=tmp;
			}
			else
				dis[v]=-1;
		}
	return cost;
}
int Dinic()
{
	int ans=0;
	while(bfs())
		ans+=dfs(s,inf);
	return ans;
}
int cnt1,cnt2;
void dfs1(int x)
{
	f[x]=1;
	cnt1++;
	for(int i=adj[x];~i;i=e[i].pre)
		if(!f[e[i].v]&&e[i].w)
			dfs1(e[i].v);
}
void dfs2(int x)
{
	f1[x]=1;
	cnt2++;
	for(int i=adj[x];~i;i=e[i].pre)
		if(!f1[e[i].v]&&e[i^1].w)
			dfs2(e[i].v);
}
int main()
{
	while(~scanf("%d%d%d%d",&n,&m,&s,&t),n)
	{
		int i,j,k;
		num=0;
		memset(adj,-1,sizeof(adj));
		while(m--)
		{
			scanf("%d%d%d",&i,&j,&k);
			insert(i,j,k);
		}
		Dinic();
		memset(f,0,sizeof(f));
		memset(f1,0,sizeof(f1));
		cnt1=cnt2=0;
		dfs1(s);
		dfs2(t);
		puts(cnt1+cnt2==n?"UNIQUE":"AMBIGUOUS");
	}
}