CF 847 J - Students Initiation

問題

Problem - J - Codeforces

問題概要

頂点辺の無向グラフが与えられる。この各辺について、どちらかに向きを付けなければならない。その時に各頂点からの出次数の最大値が最小になるような割り当て方を答えよ。

• 
• 
• 多重辺や自己ループはない

アイデア

各辺について、端点のどちらかに+1をする時に、頂点の持つ値の最大値を最小化するというように見ることが出来る。答えを二分探索することを考える。各頂点はまでは増やすことを許すとする。このが妥当かどうかをフローを使って解く。フローを考えるグラフは次のように構築する：

• から、へ容量1
• から、とへそれぞれ容量1
• から、へ容量

このようなグラフを構築し、最大フローを求める。その値がに一致すればOKとなる。このフローは、Dinicを使えば高速に動作する(のとき、Karzanov's theoremにより、Dinicはで動作するらしい(?)。この辺は理解しきれてない)。

復元は、残余グラフを見れば簡単にできる。

実装(C++)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define fi first
#define se second

// (行き先,容量,逆辺)
struct edge{ int to,cap,rev; };

const int MAX_V = 10010; // TODO:initialize
const int F_INF = 19191919; // TODO:initialize
vector<edge> G[MAX_V];
int level[MAX_V]; // sからの距離
int iter[MAX_V]; // どこまで調べ終わったか

void add_edge(int from, int to, int cap){
    G[from].pb({to,cap,(int)G[to].size()});
    G[to].pb({from,0,(int)G[from].size()-1});
}

void dinic_bfs(int s){
    memset(level,-1,sizeof(level));
    queue<int> que;
    level[s]=0;
    que.push(s);
    while(!que.empty()){
        int v = que.front();
        que.pop();
        rep(i,G[v].size()){
            edge &e = G[v][i];
            if(e.cap>0 && level[e.to]<0){
                level[e.to] = level[v]+1;
                que.push(e.to);
            }
        }
    }
}

// 増加パスをdfsで探す
int dinic_dfs(int v, int t, int f){
    if(v==t) return f;
    for(int &i=iter[v]; i<(int)G[v].size(); ++i){
        edge &e=G[v][i];
        if(e.cap>0 && level[v]<level[e.to]){
            int d = dinic_dfs(e.to,t,min(f,e.cap));
            if(d>0){
                e.cap -= d;
                G[e.to][e.rev].cap += d;
                return d;
            }
        }
    }
    return 0;
}

// sからtへの最大流
int max_flow(int s, int t){
    int flow = 0;
    while(1){
        dinic_bfs(s);
        if(level[t]<0) return flow;
        memset(iter,0,sizeof(iter));
        int f;
        while((f=dinic_dfs(s,t,F_INF))>0) flow+=f;
    }
}

using pi = pair<int,int>;

int main()
{
    int n,m;
    cin >>n >>m;

    vector<pi> e(m);
    rep(i,m)
    {
        cin >>e[i].fi >>e[i].se;
        --e[i].fi; --e[i].se;
    }

    int ng=-1, ok=5000;
    vector<pi> ans;
    while(ok-ng>1)
    {
        rep(i,MAX_V) G[i].clear();
        int mid=(ng+ok)/2;

        int S=n+m+1, T=S+1;
        rep(i,m) add_edge(S,n+i,1);
        rep(i,m)
        {
            add_edge(n+i,e[i].fi,1);
            add_edge(n+i,e[i].se,1);
        }
        rep(i,n) add_edge(i,T,mid);

        if(max_flow(S,T)==m)
        {
            ok=mid;

            ans.clear();
            rep(i,m)
            {
                for(const auto &E:G[n+i])
                {
                    if(E.cap==0)
                    {
                        int from = E.to;
                        int to = e[i].fi+e[i].se-from;
                        ans.pb({from+1,to+1});
                        break;
                    }
                }
            }
        }
        else ng=mid;
    }

    cout << ok << endl;
    rep(i,m) cout << ans[i].fi << " " << ans[i].se << endl;
    return 0;
}