GCJ Round 1B Problem C. Technobabble

この問題とは関係ないですが windows でそれっぽくプログラミングができるようになりました。

問題

Dashboard - Round 1B 2016 - Google Code Jam

前半, 後半に分かれたワードの組が N 個与えられる。
あるワードの組 (s, t) について, 「すでに s と同じ文字列が前半ワードとして登場している」かつ「すでに t と同じ文字列が後半ワードとして登場している」が成り立つとき, カウントを 1 足すことにする

N 個のワードの組をいい感じに並び替えることによって, カウントの値を最大化せよ。

解法

細かい順番は関係なしに,
「登場済みフラグを立てるための文字の組」と「カウントを稼ぐ文字の組」の 2 グループに分ければ良いです。

一回すべてのワードが登場済みになれば, あとは文字を入れるごとにカウントが 1 増えていくので, 「登場済みフラグを立てるための文字の組」を最小化すれば良いことに気付きます。あとはこれが解ければ勝ちです。

ところで, ワードの組 (former[i], after[i]) について 二部グラフを作ることを考えると, 上記の問題は最小辺カバーであることがわかります。(最小辺カバー) + (最大マッチング)= (マッチングに登場する頂点の数) が成り立つので, 結局最大流の問題になり, 解くことができます。

void solve() {
	int N;
	cin >> N;
	vector<string> former(N), after(N);
	for (int i = 0; i < N; i++) {
		cin >> former[i] >> after[i];
	}
	map<string, int> fp, ap;
	for (int i = 0; i < N; i++) {
		fp[former[i]] = 0;
		ap[after[i]] = 0;
	}
	{
		int k = 0;
		for (auto& p : fp) 
			p.second = k++;
	}
	{
		int k = 0;
		for (auto& p : ap) 
			p.second = k++;
	}
	int s = fp.size() + ap.size();
	int t = s+1, V = t+1;
	Dinic dinic(V);
	for (int i = 0; i < N; i++) {
		int v = fp[former[i]], u = fp.size() + ap[after[i]];
		dinic.add_edge(v, u, 1);
	}
	for (int i = 0; i < fp.size(); i++) dinic.add_edge(s, i, 1);
	for (int i = 0; i < ap.size(); i++) dinic.add_edge(i+fp.size(), t, 1);
	cout << N-(s-dinic.max_flow(s, t)) << endl;
}

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int T;
	cin >> T;
	for (int t = 1; t <= T; t++) {
		cout << "Case #" << t << ": " ;
		solve();
	}
	return 0;
}