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

Published on 2015-12-25

题目地址

描述

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

样例输入

2
6 8
1 3 U
1 4 U
2 4 U
2 5 D
3 4 D
4 5 U
5 6 D
5 6 U
4 4
1 2 D
1 4 D
2 3 U
3 4 U

样例输出

1 3 4 2 5 6 5 4 1

No euler circuit exist

附加输入

11

6 8
1 2 U
2 3 U
3 4 U
4 5 U
2 5 D
2 6 U
6 4 U
4 1 U

6 13
1 2 U
1 3 U
1 3 U
1 4 U
2 3 U
2 5 D
2 5 U
5 3 D
5 6 U
6 3 U
4 6 U
4 6 U
3 4 U


6 13
1 2 U
1 3 U
1 3 U
1 4 U
2 3 U
2 5 D
2 5 U
5 3 D
5 6 U
6 3 D
4 6 U
4 6 U
3 4 U

6 12
1 2 U
1 2 U
2 3 U
2 3 U
3 4 U
3 4 U
4 5 D
4 5 D
5 6 U
5 6 U
6 1 U
6 1 U

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


4 4
1 2 D
2 3 D
3 4 D
4 1 D

4 8
1 2 D
1 2 U
3 2 D
3 2 U
3 4 U
3 4 U
4 1 U
4 1 U

6 8
1 3 U
1 4 U
2 4 U
2 5 D
3 4 D
4 5 U
5 6 D
5 6 U

4 4
1 2 D
1 4 D
2 3 U
3 4 U

1 1
1 1 D

1 4
1 1 D
1 1 U
1 1 D
1 1 U

附加输出

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

分析

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