UVa 10735 - Euler Circuit(混合图欧拉回路)

#图论 #欧拉回路

Published on 2015-12-25

描述

给出一个 $V(V\le100)$ 个点和 $E(E\le500)$ 条边的无向边与有向边的混合图，试打印出它的任意一条欧拉回路（无向边的两个方向只能从某个方向经过一次），如果没有输出 No euler circuit exist。输入保证图连通。

样例输入

样例输出

1 3 4 2 5 6 5 4 1

No euler circuit exist

附加输入

附加输出

1 2 5 4 3 2 6 4 1

1 2 5 3 1 4 6 5 2 3 4 6 3 1

1 2 5 3 1 4 6 3 4 6 5 2 3 1

1 2 3 4 5 6 1 2 3 4 5 6 1

1 2 3 1 4 5 1

1 2 3 4 1

1 2 1 4 3 2 3 4 1

1 3 4 2 5 6 5 4 1

No euler circuit exist

1 1

1 1 1 1 1

分析

这题是欧拉回路，那就是说从任何一点出发都可以经过所有边恰好一次再回到自己，混合图中无向图定向后，有欧拉回路当且仅当所有点的入度都等于出度。
因为图联通，我们无需额外加入判断图是否联通。首先我们将所有的无向边随便定向，计算得到每个点的出度与入度之差 $\mathrm{degree}$ ，可以发现，如果某个点 $v$ 的 $\mathrm{degree}$ 是奇数，那么肯定不存在欧拉回路，因为我们无论怎么改变经过它的边的方向，它的 $\mathrm{degree}$ 会一口气变化 $2$ ，仍然是奇数。
那么问题就回到了如何将这些无向边定向，使得所有点的 $\mathrm{degree}$ 为 $0$ ，利用网络流解决。
建立源点汇点 $S,T$ 。对于那些 $\mathrm{degree} > 0$ 的点 $v$ ，我们连一条边 $S\rightarrow v$ ，容量为， $\frac{\mathrm{degree}(v)}{2}$ ，原因是改变一条从其出去的边的方向其度数会减小 $2$ ,所以至多也必须改变 $\frac{\mathrm{degree}(v)}{2}$ 条从其出去的边。对于那些 $\mathrm{degree} < 0$ 的点 $v$ ，我们连一条边 $v\rightarrow T$ ，容量为 $\frac{-\mathrm{degree}(v)}{2}$ ，原因是改变一条进入它的边的方向其度数会增加 $2$ ，所以至多也必须改变 $\frac{-\mathrm{degree}(v)}{2}$ 条从其出去的边。而原图中的无向边按照开始的方向添加进去，容量为 $1$ ，表示方向只能改变一次；有向边无法改变方向，不添加进去。接着跑网络流就行了，如果从 $S$ 出发的边满流了，说明所有的点的 $\mathrm{degree}$ 值成功修改为 $0$ ，因为所有 $\mathrm{degree} > 0$ 的点等于 $0$ 了，根据对称性所有 $\mathrm{degree} < 0$ 的点也等于 $0$ 了；而在网络中间的那些点，根据流量不会积压原则，流入量都等于流出量，其值仍然为 $0$ ，所以这样是可行的。
接着把网络流中之前我们放进去待确定方向的无向边添加到原图，这时它们已经被成功定向了：对于流量为 $1$ 的边，反向放入，否则方向不变。最后打印欧拉回路即可，注意有重边。
另外，此题是二分图匹配 Intermediate 中的一道题，但博主还没有考虑清楚二分图匹配的解法，如果谁掌握了运用二分图匹配的解法，不妨在下面留言。我将虚心求教。

代码

//  Created by Sengxian on 12/25/15.
//  Copyright (c) 2015年 Sengxian. All rights reserved.
//  UVa 10735 混合图的欧拉回路 网络流建图求解
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
using namespace std;
const int maxn = 100 + 3;
struct edge {
    int to, cap, rev;
    bool real;
    edge(int to, int cap, int rev, bool real): to(to), cap(cap), rev(rev), real(real) {}
};
struct Dinic {
    static const int maxNode = 100 + 3, INF = 0x3f3f3f3f;
    vector<edge> G[maxNode];
    int s, t;
    int iter[maxNode], level[maxNode];
    inline void init(int n) {
        for(int i = 0; i < n; ++i) G[i].clear();
    }
    inline void addEdge(int f, int t, int c) {
        G[f].push_back(edge(t, c, G[t].size(), 1));
        G[t].push_back(edge(f, 0, G[f].size() - 1, 0));
    }
    int Bfs() {
        queue<int> q;
        q.push(s);
        memset(level, -1, sizeof(level));
        level[s] = 0;
        while(!q.empty()) {
            int u = q.front(); q.pop();
            for(int i = 0; i < G[u].size(); ++i) {
                edge &e = G[u][i];
                if(e.cap > 0 && level[e.to] == -1) {
                    level[e.to] = level[u] + 1;
                    q.push(e.to);
                }
            }
        }
        return ~level[t];
    }
    int Dfs(int u, int flow) {
        if(u == t || flow == 0) return flow;
        for(int &i = iter[u]; i < G[u].size(); ++i) {
            edge &e = G[u][i];
            if(level[e.to] == level[u] + 1 && e.cap > 0) {
                int d = Dfs(e.to, min(flow, e.cap));
                if(d > 0) {
                    e.cap -= d;
                    G[e.to][e.rev].cap += d;
                    return d;
                }
            }
        }
        return 0;
    }
    int maxFlow(int s, int t) {
        this -> s = s, this -> t = t;
        int flow = 0, d;
        while(Bfs()) {
            memset(iter, 0, sizeof(iter));
            while((d = Dfs(s, INF)) > 0) flow += d;
        }
        return flow;
    }
}Solver;
struct eg {
    int to;
    bool vis;
    eg(int to, bool vis = 0): to(to), vis(vis) {}
};
vector<eg> G[maxn];
int n, m, degree[maxn];
stack<int> stk;
void euler(int u) {
    for(int i = 0; i < G[u].size(); ++i) {
        eg &e = G[u][i];
        if(!e.vis) {
            e.vis = true;
            euler(e.to);
            stk.push(u);
        }
    }
}

inline int ReadInt() {
    int n = 0, ch = getchar();
    while(ch < '0' || ch > '9') ch = getchar();
    do {
        n = n * 10 + ch - '0';
        ch = getchar();
    }while(ch >= '0' && ch <= '9');
    return n;
}
int main() {
    int caseNum = ReadInt(), f, t, ch;
    for(int k = 0; k < caseNum; ++k) {
        if(k) printf("\n");
        n = ReadInt(), m = ReadInt();
        fill(degree, degree + n, 0);
        Solver.init(n + 2);
        for(int i = 0; i < n; ++i) G[i].clear();

        int S = n, T = n + 1;
        for(int i = 0; i < m; ++i) {
            f = ReadInt() - 1, t = ReadInt() - 1, ch = getchar();
            degree[f]++; degree[t]--; //degree 表示出度减去入度，这里无向边是随便定向的
            if(ch == 'U') Solver.addEdge(f, t, 1);
            else G[f].push_back(eg(t));
        }

        bool flag = false; int flow = 0;
        for(int i = 0; i < n; ++i) {
            if(degree[i] % 2 == 1) {
                flag = true; //由于是欧拉回路，不能有任何出度不等于入度的的点，在这里判断是否是奇数（无论怎么改方向，还是奇数）
                break;
            }
            if(degree[i] > 0) Solver.addEdge(S, i, degree[i] / 2), flow += abs(degree[i]) / 2;
            else if(degree[i] < 0) Solver.addEdge(i, T, -degree[i] / 2);
        }

        if(flag || Solver.maxFlow(S, T) != flow) {
            puts("No euler circuit exist");
            continue;
        }
        for(int i = 0; i < n; ++i)
            for(int j = 0; j < Solver.G[i].size(); ++j) {
                edge &e = Solver.G[i][j];
                if(e.real && e.to < n) { //将定向后的无向边加入原图
                    if(e.cap > 0) G[i].push_back(eg(e.to));
                    else G[e.to].push_back(eg(i));
                }
            }
        euler(0);
        while(!stk.empty()) {
            printf("%d ", stk.top() + 1);
            stk.pop();
        }
        printf("1\n");
    }
    return 0;
}

UVa 11997 - K Smallest Sums UVa 1327 - King's Quest

Sengxian's Blog