Chaos Slover 补档计划 - 欧拉路径

2015.11.28 18:06 Sat| 1 visits oi_2016| ChaosSlover补档计划| Text

UOJ117 欧拉回路

模板题,代码排名好高啊好评!这道题里面的细节还是不少的呢。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <bits/stdc++.h>
using namespace std;

#define N 100005
#define M 400005

int type, n, m, cnt, in[N], out[N], head[N];
bool vis[M]; stack<int> s;

inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

struct graph
{
    int next, to, val;
    graph() {}
    graph(int _next, int _to, int _val)
    : next(_next), to(_to), val(_val) {}
} edge[M];

inline void add(int x, int y, int z)
{
    edge[++cnt] = graph(head[x], y, z);
    head[x] = cnt; ++out[x], ++in[y];
}

void dfs(int x)
{
    for (int i = head[x]; i; i = head[x])
    {
        while (i && vis[abs(edge[i].val)]) i = edge[i].next;
        if (!i) return;
        vis[abs(edge[i].val)] = true;
        head[x] = edge[i].next;
        dfs(edge[i].to); s.push(edge[i].val);
    }
}

int main()
{
    cin >> type >> n >> m;
    for (int x, y, i = 1; i <= m; ++i)
    {
        x = read(), y = read(), add(x, y, i);
        if (type == 1) add(y, x, -i);
    }
    for (int i = 1; i <= n; ++i)
        if (in[i] != out[i] || (type == 1 && in[i] % 2))
            { puts("NO"); return 0; }
    dfs(edge[cnt].to);
    for (int i = 1; i <= m; ++i)
        if (!vis[i]) { puts("NO"); return 0; }
    puts("YES");
    while (!s.empty())
        printf("%d ", s.top()), s.pop();
    return 0;
}

POJ1637 Sightseeing tour

混合图的欧拉回路,网络流,前两天刚刚做完。随便给无向边确定方向,然后跑网络流找出需要给那一条边改变方向。代码链接

BZOJ2095 [Poi2010]Bridges

二分答案之后和上面一样吧……不想写了。

混合图的欧拉通路

如果有两个奇数点,加入一条从终点到起点的无向边,就可以去跑欧拉回路了。