AOJ 2251: Merry Christmas

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2251

DAGの最小パス被覆問題。パスで点を覆う際の最小本数を求める。

まず二部グラフG(V,V';E)においてDAGでvからv'に辺がある時v∈V,v'∈V'に辺を張る。
すると答えは|V|-|最大マッチング|となる。有名問題らしい。

これを証明してみよう。
グラフを観察すると|V|=(パスの本数)+(パスで使われている辺の本数)なので、
(パスで使われている辺の本数)を最大化すればよい。

ここで上の二部グラフを考えると、
「DAG上でパスが存在する<=>二部グラフ辺を選んだ時、どの点も次数が高々1になる」
が成立しており、選んだ辺の集合は二部グラフのマッチングとなっている。
なので、最大マッチングを求めればパスの最小本数も求められたことになる。

あとこの問題に少し関連がありそうなものとしてdilworthの定理というものがある。

これはDAGにおいて
(どの二つの点間にパスが存在しない(安定集合の有向版)ような頂点の部分集合の最大サイズ) = (最小パス被覆の本数)
というものである。

二部グラフの|最大安定集合|=|最小辺カバー|みたいな感じ。

int main() {
    while(true) {
        cin >> N >> M >> L;
        if(N == 0 && M == 0 && L == 0) break;
        for(int i = 0; i < N; i++) {
            for(int j = 0; j < N; j++) {
                if(i != j) E[i][j] = INF;
            }
        }
        for(int i = 0; i < M; i++) {
            int from, to, cost;
            cin >> from >> to >> cost;
            E[from][to] = cost;
            E[to][from] = cost;
        }
        for(int i = 0; i < L; i++) cin >> R[i] >> T[i];
        for(int k = 0; k < N; k++) {
            for(int i = 0; i < N; i++) {
                for(int j = 0; j < N; j++) {
                    E[i][j] = min(E[i][j], E[i][k] + E[k][j]);
                }
            }
        }
        for(int i = 0; i < L * 2; i++) G[i].clear();
        for(int i = 0; i < L; i++) {
            for(int j = 0; j < L; j++) {
                if(i == j) continue;
                if(T[j] - T[i] >= E[R[j]][R[i]]) {
                    add_edge(i, j + L);
                }
            }
        }
        cout << L - bipartite_matching() << endl;
    }
}

なぜか昔解いていた。(は？)
別解として航空スケジューリング問題に帰着するのもありそう。

POJ 2226: Muddy Fields

http://poj.org/problem?id=2226

なるべく長い板を置いていく。
あとは板の縦方向の置き方と横方向の置き方を点に、草を辺に対応させて二部グラフを作り、最小点カバーを求めれば良い。

int H, W;
int N, M;
char F[60][60];
int X[60][60];
int Y[60][60];

int main() {
	scanf("%d%d", &H, &W);
	rep(i, 0, H) scanf("%s", F[i]);
	memset(X, -1, sizeof(X));
	memset(Y, -1, sizeof(Y));

	int cnt = 0;
	rep(i, 0, H) {
		int p = 0, at = 0;
		while(true) {
			if(p == W) break;
			while(at != W && F[i][at] == '*') {
				at++;
			}
			if(p == at) {
				at++; p = at;
			}
			else {
				rep(j, p, at) X[i][j] = cnt;
				cnt++;
				p = at;
			}
		}
	}
	N = cnt;
	rep(j, 0, W) {
		int p = 0, at = 0;
		while(true) {
			if(p == H) break;
			while(at != H && F[at][j] == '*') {
				at++;
			}
			if(p == at) {
				at++; p = at;
			}
			else {
				rep(i, p, at) Y[i][j] = cnt;
				cnt++;
				p = at;
			}
		}
	}
	M = cnt - N;

	int s = N + M, t = N + M + 1;
	rep(i, 0, N) MF::add_edge(s, i, 1);
	rep(j, 0, M) MF::add_edge(j + N, t, 1);
	rep(i, 0, H) 
		rep(j, 0, W) {
			if(X[i][j] != -1 && Y[i][j] != -1) {
				MF::add_edge(X[i][j], Y[i][j], 1);
			}
		}

	printf("%lld\n", MF::get(s, t));

	return 0;
}

結構すんなりできた。だいぶマッチングはわかってきたかな。

POJ 2724: Purifying Machine

http://poj.org/problem?id=2724

omochan.hatenablog.com
↑これとほとんど同じ。
一気に*を使って消せるやつ同士に辺を張ったグラフは2部グラフとなる。
2部グラフになるためには任意のサイクルの大きさが偶数であればよいが、Nコのbitのうち1つ変えるという作業を繰り返し行うとき、元に戻るためには偶数回である必要がある。よってこの条件を満たす。
あとはフローを流して最小辺カバーを求めれば良い。その際グラフの点の個数を二倍にすると楽。

二部グラフから考えるというよりは、このグラフの最大マッチング求めたいな…ところでこのグラフは二部グラフじゃん!みたいな感じかな。

int N, M;
char s[20];
bool MP[MAX_N][MAX_N];
bool A[MAX_N];

int main() {
	rep(bit, 0, (1 << 10)) {
		rep(i, 0, 10) {
			if(bit & (1 << i)) MP[bit][bit - (1 << i)] = true;
			else MP[bit][bit | (1 << i)] = true;
		}
	}

	while(true) {
		scanf("%d%d", &N, &M);
		if(N == 0 && M == 0) break;
		memset(A, 0, sizeof(A));

		rep(i, 0, M) {
			scanf("%s", s);
			int v1 = 0, v2 = 0;
			rep(i, 0, N) {
				if(s[i] == '*') v1 += (1 << i);
				else if(s[i] == '1') {
					v1 += (1 << i);
					v2 += (1 << i);
				}
			}
			A[v1] = true; A[v2] = true;
		}

		MF::init((1 << (N + 1)) + 2);
		int s = (1 << (N + 1)), t = (1 << (N + 1)) + 1;

		int V = 0;
		rep(i, 0, (1 << N)) {
			if(A[i]) {
				V++;
				MF::add_edge(s, i, 1);
				MF::add_edge(i + (1 << N), t, 1);
			}
		}

		rep(i, 0, (1 << N)) {
			if(!A[i]) continue;
			rep(j, 0, (1 << N)) {
				if(A[j] && MP[i][j]) {
					MF::add_edge(i, j + (1 << N), 1);
				}
			}
		}
		int ans = MF::get(s, t);
		printf("%d\n", V - ans / 2);
	}
			
	return 0;
}

POJ 3692: Kindergarten

http://poj.org/problem?id=3692

男女がお互いを知っている最大の集合を求める。
これは男女がお互いを知らない、ということはない最大の集合であるので、
知り合いではない男女を辺でつないで最大安定集合を求めれば良い。
あとは|最大安定集合|=V-|最大マッチング|でできる。

最大安定集合はなんていうか否定が絡むイメージ。

bool V[MAX_N][MAX_N];
int N, M, G;

int main() {
	for(int q = 1; ; q++) {
		scanf("%d%d%d", &N, &M, &G);
		if(N == 0 && M == 0 && G == 0) break;
		memset(V, 0, sizeof(V));
		MF::init(N + M + 2);
		rep(i, 0, G) {
			int a, b; scanf("%d%d", &a, &b);
			a--; b--;
			V[a][b + N] = true;
		}
		int s = N + M, t = N + M + 1;
		rep(i, 0, N) {
			rep(j, N, M + N) {
				if(!V[i][j]) MF::add_edge(i, j, 1);
			}
		}
		rep(i, 0, N) MF::add_edge(s, i, 1);
		rep(i, 0, M) MF::add_edge(i + N, t, 1);

		printf("Case %d: %lld\n", q, N + M - MF::get(s, t));
	}


	return 0;
}

Kindergardenのミススペルだと思ったら、Kindergartenの方が正しかった…

POJ 1466: Girls and Boys

http://poj.org/problem?id=1466

最大安定集合を求める。
二部グラフになるので|最小点カバー|=|最大マッチング|、
任意のグラフについて|最小点カバー|+|最大安定集合|=|V|よりできる。
頂点を2倍にしてあげると実装が楽。

簡単な証明いろいろ。

• |最大マッチング|+|最小辺カバー|=|V|

辺を追加すると新たにカバーできる点は2つor1つor0つ。0つは明らかに無駄であり、なるべく2つずつカバーしたい。
ここで2つずつカバーできる最大回数=|最大マッチング|なので残りの点はそれらと同じ数だけの辺でカバーする。
これで最小辺カバーが得られる。よって
|最小辺カバー| = (新たに1つ点をカバーする辺)+(2つ点をカバーする辺)=(V-2*M)+M=V-M (M=|最大マッチング|)となり示せた。

• |最小点カバー|+|最大安定集合|=|V|

XがGの安定集合<=>V-XがGの点カバー を示す。
(=>)V-Xはある辺を通じてXと必ずつながっている。なぜならXの点どおしは互いに隣接しておらず、V-Xの点によって囲われているから。
(<=)もしXに隣接している2点が存在したとすると、その間の辺はカバーできておらず、V-Xが点カバーであることに矛盾。
よって|点カバー|+|安定集合|=|V|であり、点カバーが最小なら安定集合は最大となるので示せた。

• 二部グラフ(U,V)において|最大マッチング|=|最小点カバー|

最大マッチングにより|S|-|Γ(S)|を最大化、|T|-|Γ(T)|を最小化する点の集合S,Tを求められることを示す。
結論から言うと、最小カットc(A,B)にはU,V間の辺を通らないものが存在する(アルゴリズムデザイン335ページ参照)ので、その時S=A∩U,T=B∩Vとすればよい。
このとき|最小カット|=|A∩V|+|B∩U|=Γ(S)+|U|-|S|=|U|-(|S|-|Γ(S)|)となり、|U|が定数であることより示せた。
また|S|=|U|-|T|,|Γ(S)|=|V|-|Γ(T)|より|T|-|Γ(T)|が最小化されることも示せた。
あとはΓ(S)とTを点カバーの集合に使えば、最小の点でカバーできることがわかる。
ところで|Γ(S)|+|T|=|A∩V|+|B∩U|=|最小カット|=|最大マッチング|なので示せた。

int N;

int main() {
	while(scanf("%d", &N) != EOF) {
		int s = 2 * N, t = 2 * N + 1;
		MF::init(2 * N + 2);
		rep(i, 0, N) {
			int a, b;
			scanf("%d: (%d)", &a, &b);
			rep(j, 0, b) {
				int c; scanf("%d", &c);
				MF::add_edge(a, c + N, 1);
			}
			MF::add_edge(s, i, 1);
			MF::add_edge(i + N, t, 1);
		}
		printf("%lld\n", N - MF::get(s, t) / 2);
	}
	return 0;
}

POJ 1486: Sorting Slides

http://poj.org/problem?id=1486

完全マッチングに必ず使われる辺を答えればよい。
それはフローが流れた辺を削除したとき完全マッチングになるかどうかで判断すればよい。

その際に押し戻すテクを使ってN-1のフローを作り、対象の辺の容量を0にしてdfsすると高速。

フローのライブラリを少しいじるだけでできる。

フローに限らず再帰の引数でバグらせがちなので注意。特にデフォルトの値を設定するとき。

int S[MAX_N], T[MAX_N];

namespace MF { //init before you use it

	struct edge {int to, cap, rev; };

	vector<edge> G[MAX_N];
	bool used[MAX_N];

	void init(int n) {
		rep(i, 0, n) G[i].clear();
		memset(used, 0, sizeof(used));
	}

	int add_edge(int from, int to, int cap) {
		G[from].push_back((edge){to, cap, (int)G[to].size()});
		G[to].push_back((edge){from, 0, (int)G[from].size() - 1});
		return (int)G[from].size() - 1;
	}

	int dfs(int v, int t, int f, bool change = true) {
		if(v == t) return f;
		used[v] = true;
		for(int i = 0; i < (int)G[v].size(); i++) {
			edge &e = G[v][i];
			if(!used[e.to] && e.cap > 0) {
				int d = dfs(e.to, t, min(f, e.cap), change);
				if(d > 0) {
					if(change) {
						e.cap -= d;
						G[e.to][e.rev].cap += d;
					}
					return d;
				}
			}
		}
		return 0;
	}

	ll get(int s, int t) {
		ll flow = 0;
		while(true) {
			memset(used, 0, sizeof(used));
			int f = dfs(s, t, inf);
			if(f == 0) return flow;
			flow += f;
		}
	}

	bool ok(int v, int k, int n) {
		int s = 2 * n, t = 2 * n + 1;
		int u = G[v][k].to, rev = G[v][k].rev;
		G[u][rev].cap = 0;
		swap(G[s][S[v]].cap, G[G[s][S[v]].to][G[s][S[v]].rev].cap);
		swap(G[u][T[u]].cap, G[G[u][T[u]].to][G[u][T[u]].rev].cap);
		bool res = true;

		memset(used, 0, sizeof(used));
		if(dfs(s, t, inf, false)) res = false;

		G[u][rev].cap = 1;
		swap(G[s][S[v]].cap, G[G[s][S[v]].to][G[s][S[v]].rev].cap);
		swap(G[u][T[u]].cap, G[G[u][T[u]].to][G[u][T[u]].rev].cap);
		return res;
	}
}

int N;
int X1[MAX_N], Y1[MAX_N], X2[MAX_N], Y2[MAX_N];
int X[MAX_N], Y[MAX_N];

vector<pi> ans;

int main() {
	for(int q = 1; ; q++) {
		scanf("%d", &N);
		if(N == 0) break;
		rep(i, 0, N) scanf("%d%d%d%d", &X1[i], &X2[i], &Y1[i], &Y2[i]);
		rep(i, 0, N) scanf("%d%d", &X[i], &Y[i]);

		int s = 2 * N, t = 2 * N + 1;
		MF::init(2 * N + 2);
		ans.clear();

		rep(i, 0, N) {
			rep(j, 0, N) {
				if(X1[i] <= X[j] && X[j] <= X2[i] && Y1[i] <= Y[j] && Y[j] <= Y2[i]) {
					MF::add_edge(i, j + N, 1);
				}
			}
		}
		rep(i, 0, N) {
			S[i] = MF::add_edge(s, i, 1);
			T[i + N] = MF::add_edge(i + N, t, 1);
		}
		bool ok = true;
		if(MF::get(s, t) != N) ok = false;
		
		if(ok) {
			rep(i, 0, N) {
				rep(j, 0, (int)MF::G[i].size()) {
					MF::edge e = MF::G[i][j];
					//debug(i, e.to, e.cap);
					if(e.cap == 0) {
						if(MF::ok(i, j, N)) ans.push_back(pi(i, e.to));
					}
				}
			}
		}
		printf("Heap %d\n", q);
		if(ok && (int)ans.size() > 0) {
			rep(i, 0, (int)ans.size()) {
				printf("(%c,%d)%c", ans[i].fst + 'A', ans[i].sec - N + 1, i == (int)ans.size() - 1 ? '\n' : ' ');
			}
		}
		else printf("none\n");
		printf("\n");
	}
	return 0;
}

outputの形式がややこしい。問題文は読みましょう。

POJ 2112: Optimal Milking

にぶたんして最大流流す。

にぶたんの初期値を小さくしすぎてWA出した…

struct edge {int to, cap, rev; };

vector<edge> G[MAX_N];
bool used[MAX_N];

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

int dfs(int v, int t, int f) {
	if(v == t) return f;
	used[v] = true;
	for(int i = 0; i < (int)G[v].size(); i++) {
		edge &e = G[v][i];
		if(!used[e.to] && e.cap > 0) {
			int d = 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;
}

ll max_flow(int s, int t) {
	ll flow = 0;
	while(true) {
		memset(used, 0, sizeof(used));
		int f = dfs(s, t, inf);
		if(f == 0) return flow;
		flow += f;
	}
}


int K, C, M; //machine, cow
int D[250][250];

bool ok(int m) {
	memset(used, 0, sizeof(used));
	rep(i, 0, K + C + 2) {
		G[i].clear();
	}
	int s = K + C, t = K + C + 1;
	rep(i, K, K + C) {
		rep(j, 0, K) {
			if(D[i][j] <= m) {
				//debug(m, i, j, D[i][j]);
				add_edge(i, j, 1);
			}
		}
	}
	rep(i, K, K + C) add_edge(s, i, 1);
	rep(i, 0, K) add_edge(i, t, M);
	return max_flow(s, t) == C;
}

int main() {
	scanf("%d%d%d", &K, &C, &M);
	rep(i, 0, K + C) {
		rep(j, 0, K + C) {
			scanf("%d", &D[i][j]);
			if(i == j) D[i][j] = 0;
			else if(D[i][j] == 0) D[i][j] = inf;
		}
	}

	rep(k, 0, K + C) {
		rep(i, 0, K + C) {
			rep(j, 0, K + C) {
				MIN(D[i][j], D[i][k] + D[k][j]);
			}
		}
	}

	/*
	rep(i, 0, K + C) {
		debug(vi(D[i], D[i] + K + C));
	}
	*/

	int lv = 0, rv = 100000;
	while(rv - lv > 1) {
		int m = (lv + rv) / 2;
		if(ok(m)) rv = m;
		else lv = m;
	}
	printf("%d\n", rv);

	return 0;
}

難しくはないけどWA出すとフローパートが間違ってたと思っちゃうよね。
フローはクラスじゃなくてnamespaceで管理するのがいいね。