Codeforces 723E - One Way Reform

#图论 #欧拉回路
Published on 2016-11-15

题目地址

描述

给定一个 n(n≤200)n(n\le 200) 个点 m(m≤n(n−1)2)m(m\le \frac{n(n - 1)}{2}) 条边的无向图，你需要将无向图定向，使得有尽量多的点满足以这个点为起点的边的数量等于以这个点为终点的边的数量。

分析

我们先直接考虑答案，答案就是度数为偶数的点的数量，由于这是可能的最大答案（度数为奇数的点永远不可能满足条件），所以我们只需要证明这个答案是可行的。

我们对于每个联通块分别求解。
考虑这样一个事实，一个联通块中度数为奇数的点必然为偶数个：因为一条边必然产生 2 的度，所以总的度数必然是 2 的倍数。新建一个点 SS，我们考虑将度数为奇数的点向 SS 连接一条无向边，那么新图中所有的点的度数均为偶数（包括 SS），根据欧拉回路的判断条件，从任意一个点出发必然存在一条路径 PP，使得恰好经过所有点一次，并最终回到这个点。我们考虑将边的顺序定向为路径 PP 中经过这条边的顺序，不难发现，所有点均满足“这个点为起点的边的数量等于以这个点为终点的边的数量”，而如果我们去掉 SS 这个点，剩下的只有在原图中度数为偶数的点满足条件。这就构造出了一个可行的方案。

实现比较简单，注意不要输出端点为 SS 的边。

代码

//  Created by Sengxian on 2016/11/14.
//  Copyright (c) 2016年 Sengxian. All rights reserved.
//  Codeforces 723E 欧拉回路
#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 200 + 3;
bool G[MAX_N][MAX_N], vis[MAX_N][MAX_N], vis2[MAX_N];
int n, m, d[MAX_N];

void dfs(int u) {
    vis2[u] = true;
    for (int v = 0; v <= n; ++v) if (G[u][v] && !vis[u][v]) {
        vis[u][v] = vis[v][u] = true;
        if (u != n && v != n) printf("%d %d\n", u + 1, v + 1);
        dfs(v);
    }
}

int main() {
#ifdef DEBUG
    freopen("test.in", "r", stdin);
#endif
    int caseNum;
    scanf("%d", &caseNum);
    while (caseNum--) {
        scanf("%d%d", &n, &m);
        memset(G, 0, sizeof G);
        memset(vis, 0, sizeof vis);
        memset(vis2, 0, sizeof vis2);
        memset(d, 0, sizeof d);
        for (int i = 0, u, v; i < m; ++i) {
            scanf("%d%d", &u, &v), u--, v--;
            G[u][v] = G[v][u] = true, d[u]++, d[v]++;
        }
        int ans = n;
        for (int i = 0; i < n; ++i) if (d[i] & 1)
            G[n][i] = G[i][n] = 1, ans--;
        printf("%d\n", ans);
        for (int i = 0; i <= n; ++i) if (!vis2[i])
            dfs(i);
    }
    return 0;
}
百练 3468 - 电池的寿命