POJ 1637 Sigitseeing tour

题目大意

　　有一张$n$个结点，$m$条混合边的图（$1 leq n leq 200$，$1 leq m leq 1000$），求这张图是否存在欧拉回路。

题解

　　因为有混合边，所以我们要先给无向边随机定向，然后再调整方向。

　　随机定向之后，我们就得到一张有向图。

　　我们记录每个结点的入度$ind[i]$和出度$outd[i]$，根据欧拉路的性质可以得到，当$ind[i] + outd[i]$为奇数时，一定不存在欧拉路。

　　对于建边过程，因为原有的有向边不能变向，所以我们可以忽略，只需要将读入的无向边随机定向成有向边即，设容量为$1$即可（每条边只能走一次）。

　　对于每一个$ind[i] leq outd[i]$的结点$i$，我们都从源点$s$向$i$连一条有向边，容量为$frac{outd[i] - ind[i]}{2}$；对于$ind[i] > outd[i]$的结点$i$，从$i$向$t$连一条有向边，容量为$frac{ind[i] - outd[i]}{2}$。这两种边的含义是连接结点$i$的边中，需要变向的边数。

　　显然，我们从$s$开始跑一次最大流，最后判断与$s$或$t$相连的边是否满流即可。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>

#define MAX_N (200 + 5)
#define MAX_M (1000 + 5)

using namespace std;

struct Edge
{
    int to;
    int weight;
    int next;
};

int T;
int n, m;
int s, t;
int h[MAX_N], tot = 1;
Edge e[MAX_N + MAX_M << 1];
int ind[MAX_N], outd[MAX_N];
int dep[MAX_N];
int cur[MAX_N];
queue <int> q;
int maxflow;

inline void AddEdge(int u, int v, int w)
{
    e[++tot].to = v;
    e[tot].weight = w;
    e[tot].next = h[u];
    h[u] = tot;
    return;
};

bool BFS()
{
    memset(dep, 0x7f, sizeof dep);
    memcpy(cur, h, sizeof cur);
    q.push(s);
    dep[s] = 0;
    int u, v, w;
    while(!q.empty())
    {
        u = q.front();
        q.pop();
        for(int i = h[u]; i; i = e[i].next)
        {
            v = e[i].to;
            w = e[i].weight;
            if(dep[v] > dep[u] + 1 && w)
            {
                dep[v] = dep[u] + 1;
                q.push(v);
            }
        }
    }
    return dep[t] != 0x7f7f7f7f;
}

int DFS(int u, int flow)
{
    if(u == t)
    {
        maxflow += flow;
        return flow;
    }
    int v, w;
    int tmp, sum = 0;
    for(int i = cur[u]; i && flow; i = e[i].next)
    {
        cur[u] = i;
        v = e[i].to;
        w = e[i].weight;
        if(dep[v] == dep[u] + 1 && w && (tmp = DFS(v, min(flow, w))))
        {
            e[i].weight -= tmp;
            e[i ^ 1].weight += tmp;
            sum += tmp;
            flow -= tmp;
        }
    }
    return sum;
}

void Dinic()
{
    while(BFS()) DFS(s, 0x7f7f7f7f);
    return;
}

int main()
{
    scanf("%d", &T);
    while(T--)
    {
        memset(h, 0, sizeof h);
        memset(ind, 0, sizeof ind);
        memset(outd, 0, sizeof outd);
        tot = 1;
        maxflow = 0;
        scanf("%d%d", &n, &m);
        s = 0;
        t = n + 1;
        int u, v, d;
        for(int i = 1; i <= m; ++i)
        {
            scanf("%d%d%d", &u, &v, &d);
            ++outd[u];
            ++ind[v];
            if(!d) 
            {
                AddEdge(u, v, 1);
                AddEdge(v, u, 0);
            }
        }
        bool isEuler = true;
        for(int i = 1; i <= n; ++i)
        {
            if(ind[i] + outd[i] & 1) 
            {
                isEuler = false;
                break;
            }
        }
        if(!isEuler) 
        {
            printf("impossible
");
            continue;
        }
        int tmp = tot;
        for(int i = 1; i <= n; ++i)
        {
            if(ind[i] <= outd[i]) 
            {
                AddEdge(s, i, outd[i] - ind[i] >> 1);
                AddEdge(i, s, 0);
            }
            else
            {
                AddEdge(i, t, ind[i] - outd[i] >> 1);
                AddEdge(t, i, 0);
            }
        }
        Dinic();
        for(int i = tmp + 1; i <= tot; i += 2)
        {
            if(e[i].weight)
            {
                isEuler = false;
                break;
            }
        }
        if(!isEuler) printf("impossible
");
        else printf("possible
");
    }
    return 0;
}