Learning Algorithms

アルゴリズムの勉強メモ

CF Round #375 Div.2 E. One-Way Reform

Codeforces Round #375 Div.2 E問題

Problem - E - Codeforces

与えられた単純無向グラフに対して、入次数と出次数が等しい頂点の数が最大化されるように各辺に向きをつける、という問題。連結とは限らないことに注意する。辺の追加はできないので、そもそも次数が奇数である頂点は条件を満たす頂点にはなりえない。まず例によって次数が奇数である頂点同士を無向辺でつなぐことで、すべての頂点の次数を偶数にすることを考える。このグラフは、オイラー路を構成できる。するとすべての頂点について、条件を満たすことになる。辺を加えたのは、もともと次数が奇数だった頂点同士のみだったので、もともと次数が偶数だった頂点については、このオイラー路によってできる辺の向きで条件を満たすことになる。よって求める最大値はnから次数が奇数である頂点数を引いた数になり、加えた辺以外のオイラー路のパスを出力すれば良い。グラフが非連結である場合に注意してそれぞれの連結部分でオイラー路を構成した。隣接リストで実装したが、すごく煩雑になったので、隣接行列で実装すべきだった( n <= 200だったからそりゃそうか)。

#include "bits/stdc++.h"
using namespace std;
#define OUT(x)                cout << #x << " = " << x << endl; 
#define rep(i, n)             for (int (i) = 0; (i) < (int)(n); (i)++)
#define rer(i, l, r)          for (int (i) = (int)(l); (i) <= (int)(r); (i)++)
#define reu(i, l, r)          for (int (i) = (int)(l); (i) < (int)(r); (i)++)
#define each(i, v)            for (auto i : v)
#define all(x)                (x).begin(), (x).end()
#define rall(x)               (x).rbegin(), (x).rend()
#define pb(x)                 push_back(x)
#define bp(x)                 __builtin_popcount(x)
#define mp(x, y)              make_pair((x), (y))
#define fi                    first
#define se                    second
#define setp(x)               setprecision(x)
#define mset(m, v)            memset(m, v, sizeof(m))
#define sz(x)                 (int)(x.size())
static const int INF        = 0x3f3f3f3f;
static const long long INFL = 0x3f3f3f3f3f3f3f3fLL;
static const int MOD        = 1000000007;
static const double PI      = 3.14159265358979;

//#define int                   long long

typedef vector<double>        vd;
typedef vector<string>        vs;
typedef vector<bool>          vb;
typedef vector<int>           vi;
typedef pair<int, int>        pii;
typedef vector<pii>           vpii;

template<typename T> void pv(T a, T b) { for (T i = a; i != b; i ++) cout << *i << " "; cout << endl; }
template<typename T, typename U> inline void amin(T &x, U y) { if (y < x) x = y; }
template<typename T, typename U> inline void amax(T &x, U y) { if (x < y) x = y; }
int in() { int _x; cin >> _x; return _x; }

vi g[220];
vi path;

//無向グラフからオイラー路を作る
void visit(int s, vi& path) {
        while (!g[s].empty()) {
                int next = g[s].back();
                g[s].pop_back();
                rep(j, sz(g[next])) {
                        if (g[next][j] == s) {
                                g[next].erase(g[next].begin() + j);
                                break;
                        }
                }
                visit(next, path);
        }
        path.pb(s);
}
      
signed main() { 
        int t;
        cin >> t;
        while (t --) {
                int n, m;
                cin >> n >> m;
                rep(i, 220) g[i].clear();
                rep(i, m) {
                        int a, b;
                        cin >> a >> b;
                        a --, b --;
                        g[a].pb(b);
                        g[b].pb(a);
                }
                vi odd;
                int ans = n;
                rep(i, n) if (sz(g[i]) & 1) {
                        odd.pb(i);
                        ans --;//次数が奇数でないものの数
                }
                vi crash[220];
                rep(i, sz(odd)) {
                        g[odd[i]].pb(odd[i + 1]);//次数が奇数の頂点同士を繋ぐ
                        g[odd[i + 1]].pb(odd[i]);
                        crash[odd[i + 1]].pb(odd[i]);//あとで壊すため(構成したオイラー路のうち、本来無い辺)
                        crash[odd[i]].pb(odd[i + 1]);
                        i ++;
                }
                path.clear();
                rep(i, n) {
                        if (!g[i].empty()) {
                                visit(i, path);
                                path.pb(-1);//非連結な部分を-1で区別する
                        }
                }
                reverse(all(path));
                cout << ans << endl;
                rep(i, sz(path) - 1) {
                        if (path[i] == -1 || path[i + 1] == -1) continue;//-1のときは連結部分の境目
                        bool f = true;
                        rep(j, sz(crash[path[i]])) {
                                if (crash[path[i]][j] == path[i + 1]) {
                                        f = false;//crashコンテナに入っている辺なら出力してはいけない
                                        crash[path[i]].erase(crash[path[i]].begin() + j);
                                        rep(k, sz(crash[path[i + 1]])) {
                                                if (crash[path[i + 1]][k] == path[i]) {
                                                        crash[path[i + 1]].erase(crash[path[i + 1]].begin() + k);
                                                }
                                        }
                                }
                        }
                        if (f) cout << path[i] + 1 << ' ' << path[i + 1] + 1 << endl;
                }
        }
        return 0;
}               

もうちょっときれいに書きたい。。。


追記

隣接行列による実装。めっちゃ書きやすかった。

#include "bits/stdc++.h"
using namespace std;
#define OUT(x)                cout << #x << " = " << x << endl; 
#define rep(i, n)             for (int (i) = 0; (i) < (int)(n); (i)++)
#define rer(i, l, r)          for (int (i) = (int)(l); (i) <= (int)(r); (i)++)
#define reu(i, l, r)          for (int (i) = (int)(l); (i) < (int)(r); (i)++)
#define each(i, v)            for (auto i : v)
#define all(x)                (x).begin(), (x).end()
#define rall(x)               (x).rbegin(), (x).rend()
#define pb(x)                 push_back(x)
#define bp(x)                 __builtin_popcount(x)
#define mp(x, y)              make_pair((x), (y))
#define fi                    first
#define se                    second
#define setp(x)               setprecision(x)
#define mset(m, v)            memset(m, v, sizeof(m))
#define sz(x)                 (int)(x.size())
static const int INF        = 0x3f3f3f3f;
static const long long INFL = 0x3f3f3f3f3f3f3f3fLL;
static const int MOD        = 1000000007;
static const double PI      = 3.14159265358979;

//#define int                   long long

typedef vector<double>        vd;
typedef vector<string>        vs;
typedef vector<bool>          vb;
typedef vector<int>           vi;
typedef pair<int, int>        pii;
typedef vector<pii>           vpii;

template<typename T> void pv(T a, T b) { for (T i = a; i != b; i ++) cout << *i << " "; cout << endl; }
template<typename T, typename U> inline void amin(T &x, U y) { if (y < x) x = y; }
template<typename T, typename U> inline void amax(T &x, U y) { if (x < y) x = y; }
int in() { int _x; cin >> _x; return _x; }

int g[220][220];
vi path;
int used[220];

void visit(int s, vi& path) {
        used[s] = true;
        rep(i, 220) if (g[s][i] > 0) {
                g[s][i] --;
                g[i][s] --;
                visit(i, path);
        }
        path.pb(s);
}
      
signed main() { 
        int t;
        cin >> t;
        while (t --) {
                int n, m;
                cin >> n >> m;
                rep(i, 220) rep(j, 220) g[i][j] = 0;
                rep(i, m) {
                        int a, b;
                        cin >> a >> b;
                        a --, b --;
                        g[a][b] ++;
                        g[b][a] ++;
                }
                vi odd;
                int ans = n;
                rep(i, n) {
                        int cnt = 0;
                        rep(j, n) cnt += g[i][j];
                        if (cnt & 1) {
                                odd.pb(i);
                                ans --;
                        }
                }
                int crash[220][220] = { 0 };
                rep(i, sz(odd)) {
                        g[odd[i]][odd[i + 1]] ++;
                        g[odd[i + 1]][odd[i]] ++;
                        crash[odd[i]][odd[i + 1]] ++;
                        crash[odd[i + 1]][odd[i]] ++;
                        i ++;
                }
                rep(i, 220) used[i] = false;
                path.clear();
                rep(i, n) {
                        if (!used[i]) {
                                visit(i, path);
                                path.pb(-1);
                        }
                }
                reverse(all(path));
                cout << ans << endl;
                rep(i, sz(path) - 1) {
                        if (path[i] == -1 || path[i + 1] == -1) continue;
                        bool f = true;
                        if (crash[path[i]][path[i + 1]] > 0) {
                                f = false;
                                crash[path[i]][path[i + 1]] --;
                                crash[path[i + 1]][path[i]] --;
                        }
                        if (f) cout << path[i] + 1 << ' ' << path[i + 1] + 1 << endl;
                }
        }
        return 0;
}