题解：UVA10735 混合图的欧拉回路 Euler Circuit

dongzhenmao · 2025-11-07 11:31:23 · 题解

我不知道啊，看到有欧拉回路就进来了。提供一个不同的建模方法。

首先常用的欧拉回路算法仅支持无向图和有向图。对于一张有向图来说，他是欧拉图的充要条件是每个点的度（出度减入度）都是偶数，所以说，我们不用管具体的边，关注每个点的出入度就好了。

考虑网络流建模，每个点连的无向边中选取出边入边的条数是固定的，所以考虑拆点。

注意下文对出入点的定义与寻常不同。

对于每个点的出点，我们又源点向其连一条边，容量为其出边条数，对于每个入点，我们让她向汇点连一条容量为其入边条数的边，同时，每个出点向在原图与他有连无向边的入点连一条容量为 1 的边。

可以发现，跑完网络流之后出点向入点连的边是否使用就是新图上是否存在这条有向边（确定方向）。注意原图上的有向边必须保留。

然后再跑一遍欧拉回路即可，这种做法判无解也很清晰。

核心代码：

    for (int i = 0; i < m; ++i) {
        int x = input(), y = input(), c = getchar();
        if (c == 'U') {
            add_edge(x, y + n, 1);
            add_edge(y, x + n, 1);
            ++all[x], ++all[y];
        } else {
            _G._add_edge(x, y);
            ++d[x], --d[y];
        }
    }

    int exp = 0;

    for (int i = 1; i <= n; ++i) {
        if (abs(d[i]) > all[i] || (all[i] + d[i]) % 2 == 1) {
            puts("No euler circuit exist"); return;
        }
        int out = (all[i] + d[i]) / 2 - d[i];
        int in = all[i] - out;
        exp += out;
        add_edge(bg, i, out);
        add_edge(i + n, ed, in);
    }

    int res = 0;
    while (bfs()) {
        res += dfs(bg, inf);
    }

    if (res != exp) {
        puts("No euler circuit exist\n"); return;
    }