poj1637

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;
}