学步园

题目链接:   poj 1637

题目大意:   给出既有有向边，又有无向边的图

                  问该图是否存在欧拉回路

解题思路:   先把无向边任意定向，然后记录每个结点的出度和入度，设X=出度-入度

                  若X为奇数，就不存在欧拉回路，因为把边反向只会使得X+-2，无论如何也不能得到0

                  建立超级源点和汇点求最大流：

                  1.当前顶点的X为偶数并且小于0，源点指向该点，容量为X/2边

                  2.当前顶点的X为偶数并且大于0，该点指向汇点，容量为X/2边

                  3.把所有的无向边按原来的指向，建立边，容量为1

                  若网络流达到满流则存在欧拉回路

                  最终的结果是要使得所有顶点的出度等于入度，如果存在X不为0的情况，就需要把某些边反向

                  反向一条边，使X+2或者X-2，若能达到满流则所有会源点或汇点相连的顶点都能使得X=0

代码:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 203
#define Min(a,b) (a<b?a:b)
#define INF 0x3f3f3f3f
int S,E,visit[MAX],flag[MAX][MAX],Map[MAX][MAX],pre[MAX],Index;
int path[MAX],listb[MAX<<1],In[MAX],To[MAX];
struct snode{
    int c,to,next;
}Edge[MAX*MAX];
int Fabs(int x)
{
    return (x<0)?-x:x;
}

void Add_edge(int a,int b,int c)
{
    Edge[Index].to=b,Edge[Index].c=c;
    Edge[Index].next=pre[a];
    pre[a]=Index++;
}

bool BFS()     //BFS寻找增广路
{
    int i,s,e,v,vv;
    s=e=0;
    memset(visit,0,sizeof(visit));
    memset(flag,0,sizeof(flag));
    listb[s++]=S;
    visit[S]=1;
    while(s!=e)
    {
        v=listb[e++];
        if(v==E)
            return true;
        for(i=pre[v];i!=-1;i=Edge[i].next)
        {
            vv=Edge[i].to;
            if(!visit[vv]&&Map[v][vv]>=1)
            {
                visit[vv]=1;
                listb[s++]=vv;
                flag[v][vv]=1;
            }
        }
    }
    return false;
}

int DFS(int v,int sum)
{
    int s=sum,i,t,vv;
    if(v==E||sum==0)
        return sum;
    for(i=pre[v];i!=-1;i=Edge[i].next)
    {
        vv=Edge[i].to;
        if(flag[v][vv])
        {
            t=DFS(vv,Min(sum,Map[v][vv]));
            Map[v][vv]-=t;
            Map[vv][v]+=t;
            sum-=t;
        }
    }
    return s-sum;
}

int Solve()      //Dinic
{
    int sum=0;
    while(BFS())
        sum+=DFS(S,INF);
    return sum;
}

int main()
{
    int n,m,i,j,a,b,c,sum1,t,temp3;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        Index=sum1=0,S=0,E=n+1;
        memset(In,0,sizeof(In));
        memset(To,0,sizeof(To));
        memset(pre,-1,sizeof(pre));
        memset(Map,0,sizeof(Map));
        for(i=1;i<=m;i++)
        {
            scanf("%d%d%d",&a,&b,&c);
            To[a]++,In[b]++;
            if(c==0)     //中间建图
            {
                c=1;
                if(!Map[a][b])
                {
                    Add_edge(a,b,c);
                    Add_edge(b,a,-c);
                }
                Map[a][b]+=c;
            }
        }
        int pd=0,temp,temp1;
        for(i=1;i<=n;i++)
        {
            temp=In[i]-To[i];
            temp1=Fabs(temp);
            if(temp1!=0&&temp1%2==0)
            {
                if(temp<0)                //左边
                {
                    a=S,b=i,c=temp1/2,sum1+=c;
                    if(!Map[a][b])
                    {
                        Add_edge(a,b,c);
                        Add_edge(b,a,-c);
                    }
                    Map[a][b]+=c;
                }
                else                      //右边
                {
                    a=i,b=E,c=temp1/2;
                    if(!Map[a][b])
                    {
                        Add_edge(a,b,c);
                        Add_edge(b,a,-c);
                    }
                    Map[a][b]+=c;
                }
            }
            else if(temp1!=0)
            {
                pd=1;
                break;
            }
        }
        if(pd==1)
            printf("impossible\n");
        else
        {
            temp3=Solve();
            if(sum1==temp3)
                printf("possible\n");
            else
                printf("impossible\n");
        }
    }
}