ACM-ICPC 2016 Asia Tsukuba Regional 国内予選, H 解答

H: プレゼント交換会

問題

無向グラフがある。全ての辺に向きをつけなさい。そのとき、すべての頂点の入次数の最大値と最小値の差が最小に成るようにし、その時の最大値・最小値を出力せよ。
複数ある場合は最小値を最大化せよ。

制約

テストケース <= 10
n <= 100
m <= n*(n-1)/2

解法

各辺eについて、eの端点u, vのどちらかの頂点に1ポイント与える、とするとe, u, v全て頂点にしてeからu, vへ、流量1の辺を張ることで、このグラフのフローが辺の向き付に成る。
答えの最大値最小値をhigh, lowで決めて、全ての頂点に対してlow以上high以下のフローを流すことができるか判定する。high, lowを尺取法すれば highの上限はn-1なので、フローの判定はO(n)回。最大流に使うグラフはO(n^2)頂点・O(n^2)辺。Dinic法O(V^2E)なら、全体で、O(n^7)。二部グラフかつ、ほとんどの辺の流量が1であることを考慮し、Dinicのアルゴリズムに祈りを捧げることで高速に動くことが期待できる。

lowは無視してグラフを作ってから最大流を流す。後から、low流れていたかを逆流させて判定できる。

コード

#include<queue>
#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<cstring>
using namespace std;

typedef long long LL;
typedef vector<int> VI;

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define EACH(i,c) for(__typeof((c).begin()) i=(c).begin(),i##_end=(c).end();i!=i##_end;++i)
#define eprintf(s...)  fprintf(stderr, s)

template<class T> inline void amin(T &x, const T &y) { if (y<x) x=y; }
template<class T> inline void amax(T &x, const T &y) { if (x<y) x=y; }

struct Dinic {
    typedef int Flow;
    static const Flow INF = 1<<29;
    struct Edge {
	int src, dst;
	Flow cap;
	int rev;
    };
    typedef vector<vector<Edge> > Graph;
    Graph G;
    vector<int>len, iter;
    Dinic(int N) : G(N) {}
    void add_edge(int u, int v, Flow c) {
	G[u].push_back((Edge){ u, v, c, (int)G[v].size() });
	G[v].push_back((Edge){ v, u, 0, (int)G[u].size()-1 });
    }
    Flow dfs(int v, int s, Flow c) {
	if (v == s || c == 0) return c;
	Flow ret = 0;
	for (int &i=iter[v]; i<(int)G[v].size(); i++) {
	    Edge &e = G[v][i], &re = G[e.dst][e.rev];
	    if (re.cap > 0 && len[v] > len[e.dst]) {
		Flow f = dfs(e.dst, s, min(c-ret, re.cap));
		ret += f;
		e.cap += f; re.cap -= f;
		if (ret == c) break;
	    }
	}
	return ret;
    }
    void bfs(int s) {
	len.assign(G.size(), -1);
	queue<int>qu;
	qu.push(s);
	len[s] = 0;
	for (;!qu.empty();) {
	    int v = qu.front(); qu.pop();
	    for (int i=0; i<(int)G[v].size(); i++) {
		const Edge &e = G[v][i];
		if (e.cap > 0 && len[e.dst] == -1) {
		    len[e.dst] = len[v] + 1;
		    qu.push(e.dst);
		}
	    }
	}
    }
    Flow _flow;
    Flow flow(int source, int sink) {
	_flow = 0;
	Flow ret = 0;
	while (true) {
	    bfs(source);
	    if (len[sink] == -1) return _flow = ret;
	    iter.assign(G.size(), 0);
	    ret += dfs(sink, source, INF);
	}
    }
};
const Dinic::Flow Dinic::INF;

int N, M;
int X[10011], Y[10011];

bool ok(int LO, int HI) {
    int V_B = M, SRC = V_B + N, SNK = SRC + 1, SRC_2 = SNK + 1, SNK_2 = SRC_2 + 1;
    Dinic D(SNK_2 + 1);

    REP (i, M) {
	D.add_edge(SRC, i, 1);
	D.add_edge(i, V_B + X[i], 1);
	D.add_edge(i, V_B + Y[i], 1);
    }
    REP (i, N) {
	D.add_edge(V_B + i, SNK, HI);
    }

    int f = D.flow(SRC, SNK);
    if (f < M) return false;

    D.add_edge(SRC_2, SNK, LO * N);
    REP (i, N) {
	D.add_edge(V_B + i, SNK_2, LO);
    }

    int f2 = D.flow(SRC_2, SNK_2);
    if (f2 < (LL)LO * N) return false;
    return true;
}

int main() {
    while (scanf("%d%d", &N, &M), N|M) {
	REP (i, M) {
	    scanf("%d%d", X+i, Y+i);
	    X[i]--;
	    Y[i]--;
	}

	int LO = -1, HI = M;
	int hi = 1;
	REP (lo, N) {
	    amax(hi, lo);
	    while (hi <= N && !ok(lo, hi)) hi++;
	    if (hi == N + 1) break;

	    if (HI - LO >= hi - lo) {
		HI = hi;
		LO = lo;
	    }
	}

	printf("%d %d\n", LO, HI);
    }

    return 0;
}

日記

ライブラリを転写するだけの比較的簡単な問題。