poj1637
Time Limit: 1000MS | Memory Limit: 10000K | |
Total Submissions: 7945 | Accepted: 3327 |
Description
Input
Output
Sample Input
4 5 8 2 1 0 1 3 0 4 1 1 1 5 0 5 4 1 3 4 0 4 2 1 2 2 0 4 4 1 2 1 2 3 0 3 4 0 1 4 1 3 3 1 2 0 2 3 0 3 2 0 3 4 1 2 0 2 3 1 1 2 0 3 2 0
Sample Output
possible impossible impossible possible
此题就是求混合图是否存在欧拉回路。大家都知道存在欧拉回路的充分必要条件是每个顶点的入度=出度。
此题有个麻烦之处是存在无向边,而无向边也只能经过一次,那么问题来了,到底是从u->v呢还是v->u。
我们单独考虑这个有什么区别?
假设算作:u->v,此时u的入度为indeg,出度为outdeg
如果算作v->u,而其他边不变,那么u的入度为indeg+1,出度为outdeg-1
这样一搞就可以发现入度-出度的差变化为2,所以现在任意取一个方向每个点入度-出度的差与正确的取法(存在欧拉回路)入度-出度的差 相差2k(k为整数),而正确取法每个点入度-出度=0,因此任意取法,每个点入度-出度为偶数,因此可以利用此条件判断不能存在欧拉回路的情况,就是只要有一个点入度-出度为奇数,则无解。
对于有解情况,这里有一种很巧妙的方法,对于那些本来就是有向边的边,因为无法变化,因此我们不需要这些边,对于无向边我们任取一个方向构图,边权为1,此时每个点入度-出度均为偶数,我们如何反转某些边来使得每个点入度-出度均为0呢?
我们加两个点超级源点和超级汇点,对原图中入度>出度的边,我们将这些点连向汇点,边权为该点(入度-出度)/2,而对原图中入度<出度的边,我们将源点连向这些点,边权为(出度-入度)/2。然后跑一边dinic,如果存在满流的情况,就说明有解。
这是为什么呢?
我们这样想对于和源点相连的点,他们流入(出度-入度)/2,由于他们流出都为1,因此必有(出度-入度)/2个流出点,对应这(出度-入度)/2条边,我们如果将其反转的话,这些点的入度和出度就刚好相等了。
同理和汇点相连的点,必有(入度-出度)/2条边流入这些点,同理反转入度等于出度。
而对于那些不和源点也不和汇点相连接的点,则必有入度=出度,而在网络流算法中,这些点满足流守恒条件,因此跑完dinic后,入度还是等于出度,这样也就是构造了一个欧拉回路出来。
神奇吧!网络流还可以这么玩。。。
代码:
#include<cstdio>
#include<iostream>
#include<cstring>
#define Maxn 210
using namespace std;
int indeg[Maxn],outdeg[Maxn];
const int inf=0x3f3f3f3f;
struct line{
int to,next,cap;
}p[Maxn*Maxn];
int head[Maxn];
int q[Maxn];
int d[Maxn];
int tot;
int src,t;
int n,m;
void addedge(int a,int b,int c){
p[tot].to=b;
p[tot].next=head[a];
p[tot].cap=c;
head[a]=tot++;
}
void insert(int a,int b,int c){
addedge(a,b,c);
addedge(b,a,0);
}
bool bfs(){
memset(d,-1,sizeof d);
int s=0,e=-1;
q[++e]=src;
d[src]=0;
while(s<=e){
int u=q[s++];
for(int i=head[u];i!=-1;i=p[i].next){
int v=p[i].to;
if(d[v]==-1&&p[i].cap){
d[v]=d[u]+1;
q[++e]=v;
}
}
}
return d[t]!=-1;
}
int dfs(int u,int alpha){
if(u==t) return alpha;
int w,used=0;
for(int i=head[u];i!=-1&&used<alpha;i=p[i].next){
int v=p[i].to;
if(p[i].cap&&d[v]==d[u]+1){
w=dfs(v,min(alpha-used,p[i].cap));
used+=w;
p[i].cap-=w;
p[i^1].cap+=w;
}
}
if(!used) d[u]=-1;
return used;
}
int dinic(){
int ans=0;
src=0,t=n+1;
while(bfs())
ans+=dfs(src,inf);
return ans;
}
int main()
{
int cas,a,b,c;
cin>>cas;
while(cas--){
cin>>n>>m;
tot=0;
memset(indeg,0,sizeof indeg);
memset(outdeg,0,sizeof outdeg);
memset(head,-1,sizeof head);
for(int i=0;i<m;i++){
scanf("%d%d%d",&a,&b,&c);
outdeg[a]++;
indeg[b]++;
if(c==0) insert(a,b,1);
}
bool flag=true;
int res=0;
for(int i=1;i<=n;i++){
if((indeg[i]-outdeg[i])&1){
flag=false;
break;
}
if(indeg[i]>outdeg[i])
insert(i,n+1,indeg[i]-outdeg[i]>>1);
else if(indeg[i]<outdeg[i]){
insert(0,i,outdeg[i]-indeg[i]>>1);
res+=outdeg[i]-indeg[i]>>1;
}
}
if(!flag){
puts("impossible");
continue;
}
if(res==dinic()) puts("possible");
else puts("impossible");
}
return 0;
}