CF 723E One-Way Reform

题目描述

https://www.luogu.com.cn/problem/CF723E

简要题意：给定一个 $n$ 个点 $m$ 条边的无向图，现在需要给每条边定向，使得尽量多的点满足入度等于出度

$n\le 200$

Solution

容易发现答案最大为度数为偶数的点的个数，我们首先猜测能否构造出这样的解

考虑欧拉回路，注意到有度数为奇数的点，所以我们不能直接跑欧拉回路，但同时我们注意到度数为奇数的点的个数一定有偶数个，所以我们新建一个点，将其与所有度数为奇数的点相连，然后我们跑欧拉回路就行了

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#define maxn 210
#define maxm 50010
using namespace std;

int n, m;

struct Edge {
    int to, next; bool ext;
} e[maxm]; int c1, head[maxn], du[maxn];
inline void add_edge(int u, int v) {
    e[c1].to = v; e[c1].ext = 0; 
    e[c1].next = head[u]; head[u] = c1++;
}

vector<pair<int, int>> ans;
void dfs(int u) {
    for (int &i = head[u]; ~i; i = e[i].next) {
        int v = e[i].to; bool &ext = e[i].ext, &Ext = e[i ^ 1].ext;
        if (ext) continue; ext = Ext = 1; dfs(v); ans.emplace_back(v, u);
    }
}

void init() {
    fill(head, head + maxn, -1);
    fill(du, du + maxn, 0);
    c1 = 0;
    ans.clear(); 
}

void work() { init(); 
    cin >> n >> m; 
    for (int i = 1; i <= m; ++i) {
        int x, y; cin >> x >> y;
        ++du[x]; ++du[y];
        add_edge(x, y); add_edge(y, x); 
    } int Ans = 0; 
    for (int i = 1; i <= n; ++i) 
        if (du[i] & 1) add_edge(i, n + 1), add_edge(n + 1, i);
        else ++Ans;
    for (int i = 1; i <= n; ++i) dfs(i);
    cout << Ans << "\n"; 
    for (auto u : ans)
        if (u.first <= n && u.second <= n) cout << u.first << " " << u.second << "\n";
} 

int main() { 
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    int T; cin >> T;
    while (T--) work(); 
    return 0;
}