poj 1637 Sightseeing tour（混合歐拉回路）

第一次遇見混合歐拉回路，不懂。檢視了解題報告才了解此類問題的解法。

以下摘自： http://zhyu.me/acm/zoj-1992-and-poj-1637.html

題意：給出一個混合圖（有的邊有向，有的邊無向），問此圖是否存在歐拉回路。

先說說歐拉回路吧，起點和終點相同，經過圖G的每條邊一次，且隻經過一次的路徑稱為歐拉回路。

按照圖的不同分為：無向圖歐拉回路、有向圖歐拉回路和混合圖歐拉回路。

判斷一個圖是否存在歐拉回路：

1.無向圖：圖連通，且圖中均為偶度頂點。

2.有向圖：圖連通，且圖中所有頂點出入度相等。

3.混合圖：混合圖歐拉回路的判斷是用網絡流，實作方法：

首先對所有的無向邊随便定向，之後會進行調整。然後統計每個點的出入度，如果有某個點出入度之差為奇數，則不存在歐拉回路，因為相差為奇數的話，無論如果調整邊，都不能使得每個點的出入度相等。

現在每個點的出入度之差為偶數了，把這個偶數除以2,得x。則對每個頂點改變與之相連的x條邊的方向就可以使得該點出入度相等。如果每個點都能達到出入度相等，自然就存在歐拉回路了。

現在問題就變成了改變哪些邊的方向能讓每個點出入度相等了，構造網絡流模型。

有向邊不能改變方向，是以不添加有向邊。對于在開始的時候任意定向的無向邊，按所定的方向加邊，容量為1。源點向所有出>入的點連邊，容量為該點的x值；所有入>出的點向彙點連邊，容量為該點的x值。

建圖完成了，求解最大流，如果能滿流配置設定，則存在歐拉回路。那麼哪些邊改變方向才能得到歐拉回路呢？檢視流量配置設定，所有流量非0的邊就是要改變方向的邊。

原理是因為滿流配置設定，是以和源點相連的點一定都有x條邊流入，将這些邊反向這些點就出入度相等了，和彙點相連的亦然。沒有和源、彙相連的已經出入度相等了，當然不用修改，至此歐拉回路求解完畢。

關于這題：邊數應該開到4000以上。剛開始開2000WA了，原因，每加一條邊都有正向邊和反向邊是以最大為2000條，加上src點和des彙點的2000.

//208 KB	16 ms
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
const int VM = 205;
const int EM = 4005;
const int inf = 0x3f3f3f3f;
struct Edge
{
    int frm,to,next,cap;
}edge[EM];

int head[VM],in[VM],out[VM];
int ep,n,m,src,des;
int dep[VM];
void addedge (int cu,int cv,int cw)
{
    edge[ep].frm = cu;
    edge[ep].to = cv;
    edge[ep].cap = cw;
    edge[ep].next = head[cu];
    head[cu] = ep ++;
    edge[ep].frm = cv;
    edge[ep].to = cu;
    edge[ep].cap = 0;
    edge[ep].next = head[cv];
    head[cv] = ep ++;
}
int BFS ()
{
    int que[VM],i,front = 0,rear = 0;
    memset (dep,-1,sizeof(dep));
    que[rear++] = src;
    dep[src] = 0;
    while (front != rear)
    {
        int u = que[front++];
        front = front%VM;
        for (i = head[u];i != -1;i = edge[i].next)
        {
            int v = edge[i].to;
            if (edge[i].cap > 0&&dep[v] == -1)
            {
                dep[v] = dep[u] + 1;
                que[rear ++] = v;
                rear = rear % VM;
                if (v == des)
                    return 1;
            }
        }
    }
    return 0;
}
int dinic ()
{
    int i,res = 0,top;
    int stack[VM];
    int cur[VM];
    while (BFS())
    {
        memcpy (cur,head,sizeof (head));
        int u = src;
        top = 0;
        while (1)
        {
            if (u == des)
            {
                int min = inf,loc ;
                for (i = 0;i < top;i ++)
                    if (min > edge[stack[i]].cap)
                    {
                        min = edge[stack[i]].cap;
                        loc = i;
                    }
                for (i = 0;i < top;i ++)
                {
                    edge[stack[i]].cap -= min;
                    edge[stack[i]^1].cap += min;
                }
                res += min;
                top = loc;
                u = edge[stack[top]].frm;
            }
            for (i = cur[u];i != -1;cur[u] = i = edge[i].next)
                if (edge[i].cap != 0&&dep[u] + 1 == dep[edge[i].to])
                    break;
            if (cur[u] != -1)
            {
                stack[top ++] = cur[u];
                u = edge[cur[u]].to;
            }
            else
            {
                if (top == 0)
                    break;
                dep[u] = -1;
                u = edge[stack[--top]].frm;
            }
        }
    }
    return res;
}
int main ()
{
    #ifdef LOCAL
        freopen("in.txt","r",stdin);
    #endif
    int T,i,u,v,ops;
    scanf ("%d",&T);
    while (T --)
    {
        scanf ("%d%d",&n,&m);
        memset (head,-1,sizeof(head));
        memset (in,0,sizeof(in));
        memset (out,0,sizeof(out));
        ep = 0,src = 0,des = n + 1;
        while (m --)
        {
            scanf ("%d%d%d",&u,&v,&ops);
            out[u] ++;
            in[v] ++;
            if (!ops) addedge (u,v,1);
        }
        bool flag = true;
        for (i = 1;i <= n;i ++)
            if (abs(in[i] - out[i])&1){
                flag = false;
                break;
            }
        int sum = 0;
        if (!flag) printf ("impossible\n");
        else {
            for (i = 1;i <= n;i ++)
            {
                int w = (out[i] - in[i]) /2;
                if (w > 0){
                    sum += w;
                    addedge (src,i,w);
                }
                else addedge (i,des,-w);
            }
        if (sum == dinic()) printf ("possible\n");
        else printf ("impossible\n");
        }
    }
    return 0;
}