G - Sightseeing Tour ZOJ - 1992 (歐拉回路+Dinic網絡流）

G - Sightseeing Tour ZOJ - 1992

The city executive board in Lund wants to construct a sightseeing tour by bus in Lund, so that tourists can see every corner of the beautiful city. They want to construct the tour so that every street in the city is visited exactly once. The bus should also start and end at the same junction. As in any city, the streets are either one-way or two-way, traffic rules that must be obeyed by the tour bus. Help the executive board and determine if it's possible to construct a sightseeing tour under these constraints.

Input

On the first line of the input is a single positive integer n, telling the number of test scenarios to follow. Each scenario begins with a line containing two positive integers m and s, 1 <= m <= 200, 1 <= s <= 1000 being the number of junctions and streets, respectively. The following s lines contain the streets. Each street is described with three integers, xi, yi, and di, 1 <= xi, yi <= m, 0 <= di <= 1, where xi and yi are the junctions connected by a street. If di = 1, then the street is a one-way street (going from xi to yi), otherwise it's a two-way street. You may assume that there exists a junction from where all other junctions can be reached.

Output

For each scenario, output one line containing the text "possible" or "impossible", whether or not it's possible to construct a sightseeing tour.

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

歐拉回路是指從某結點出發，不重複地經過所有的路徑，并且最後能回到出發點的路徑;

本題就是判斷是否存在歐拉回路。

首先保證是在連通圖的前提下

無向圖

歐拉路徑：度數為奇數的點有0個或2個

歐拉回路：度數為奇數的點有0個

有向圖：

歐拉路徑：有兩個點入度不等于出度，其他點入度等于出度，且一個點入度-出度=1，另一個點出度-入度=1，出度大的為起點；或者所有點入度等于出度

歐拉回路：所有點入度等于出度

混合圖：把無向邊轉化為有邊判斷

開始時把有無向邊轉為有向邊，方向随便，權值（容量）為1，記錄每個點的出度out[i],入度in[i]，如果

（1）out[i]-in[i]為奇數，那麼無論怎麼轉換無向邊的方向都不可能讓out[i]==in[i],因為與i點相連的邊轉變方向後，out[i]-in[i]值隻能偶數倍的增減，這種情況是不可能存在歐拉回路的

（2）out[i]-in[i]為偶數，那麼需要改變與i相連的(out[i]-in[i])/2條邊的方向，才能使i的出度等于入度，是以建圖隻加入無向邊。建立源點sn=0，源點連向out[i]>in[i]的點，權值（容量）為（out[i]-in[i]）/2, 彙點為tn=n+1，out[i]<in[i]的點連向彙點tn，權值（容量）為(in[i]-out[i])/2,如果滿流，則存在歐拉回路。

為什麼？

在滿流的圖(無向邊建的有向圖，可調整邊的方向）中，如果把所有（除與源點和與彙點相連的邊外）求最大流中找到的增廣路徑經過的邊的方向都取反，那麼所有out[i]>in[i](與源點相連）的點變成out[i]==in[i]，同樣out[i]<in[i]的點變成out[i]==in[i]；如對于sn=》i ( (out[i]-in[i])/2>0) =》ti（ti={ t[i] | out[t] == in[t]}）=》j( (out[j]-in[j])/2<0) =》tn ,  =》表示多條邊，因為out[i]>in[i],是以要改變i=》t的方向，同時，為保證ti的長度等于入度，必須同時改變同等數量邊i=》j的方向。

        由此可推斷出：改變點i(out[i]>in[i])的出度的邊的方向，必須同時改變該邊所在的可行流所在的所有邊，那麼是否可以改變所有點i(out[i]>in[i])的出度的邊一半（sum）的方向，就等價于判斷最大流必須等于sum。同樣對于 (out[j]-in[j])/2<0的點，由于每一條邊既貢獻一個入度，又貢獻一個出度，是以圖中所有點的入度數的和等于所有點出度的和，那麼所有(out[j]-in[j])<0 的點數量等于 (out[i]-in[i])>0的點，那麼 (out[i]-in[i])/2==-(out[i]-in[i])/2=sum ,是以隻要sum==最大流，即滿流，就能實作所有點入度等于出度

#include<cstdio>
#include<stack>
#include<set>
#include<vector>
#include<queue>
#include<algorithm>
#include<cstring>
#include<string>
#include<map>
#include<iostream>
#include<cmath>
using namespace std;
#define inf 0x3f3f3f3f
typedef long long ll;
const int N=225;
const int mmax = 3020+ 7;
int num,n,sn,tn,m;
int head[N],cur[N],dep[N];
struct node
{
    int v,w,next;
} gra[mmax];
int in[N],out[N];
void ad(int u,int v,int w)
{
    gra[num].v=v;
    gra[num].next=head[u];
    gra[num].w=w;
    head[u]=num++;
    gra[num].next=head[v];
    gra[num].v=u;
    gra[num].w=0;
    head[v]=num++;
}
int bfs()
{
    queue<int>que;
    memset(dep,0,sizeof(dep));
    que.push(sn);
    dep[sn]=1;
    while(!que.empty())
    {
        int u=que.front();
        que.pop();
        if(u==tn)
            return 1;
        for(int i=head[u]; i!=-1; i=gra[i].next)
        {
            if(!dep[gra[i].v]&&gra[i].w>0)
            {
                dep[gra[i].v]=dep[u]+1;
                que.push(gra[i].v);
            }
        }
    }
    if(dep[tn])
        return 1;
    return 0;
}
int dfs(int u,int minl)
{
    if(u==tn)
        return minl;
    for(int &i=cur[u]; i!=-1; i=gra[i].next)
    {
        if(dep[gra[i].v]==dep[u]+1&&gra[i].w>0)
        {
            int k=dfs(gra[i].v,min(minl,gra[i].w));
            if(k>0)
            {
                gra[i].w-=k;
                gra[i^1].w+=k;
                return k;
            }
        }
    }
    return 0;
}
int danic()
{
    int ans=0;
    while(bfs())
    {
        for(int i=0; i<=tn; i++)
        {
            cur[i]=head[i];
        }
        while(int flow=dfs(0,inf))
        {
            ans+=flow;
        }
    }
    return ans;
}
void init()
{
    memset(head,-1,sizeof(head));
    memset(in,0,sizeof(in));
    memset(out,0,sizeof(out));
    num=0;
}
int main()
{
    int t,x,y,z;
    scanf("%d",&t);
    while(t--)
    {
        init();
        scanf("%d%d",&n,&m);
        for(int i=1; i<=m; i++)
        {
            scanf("%d%d%d",&x,&y,&z);
            out[x]++;
            in[y]++;
            if(z!=1)
                ad(x,y,1);
        }
        int flag=1;
        for(int i=1; i<=n; i++)
        {
            if((out[i]-in[i])%2!=0)
            {
                flag=0;
                break;
            }
        }
        if(flag==0)
            printf("impossible\n");
        else
        {
            sn=0;
            tn=n+1;
            int sum=0;
            for(int i=1; i<=n; i++)
            {
                int k=out[i]-in[i];
                if(k>0)
                {
                    ad(0,i,k/2);  //k：要改變的邊的數量
                    sum+=k/2;
                }
                else if(k<0)
                    ad(i,n+1,-k/2);
            }
            if(sum==danic()) //dani()求最大流模闆求法
                printf("possible\n");
            else
                printf("impossible\n");
        }
    }
    return 0;
}