AOJ 2168 Luigi's Tavern

問題

Luigi's Tavern | Aizu Online Judge

H 人の勇者, W 人の戦士, C 人の僧侶, M 人の魔法使いがいる。以下の条件を満たすパーティは最大いくつ作れるか。

• パーティには必ず勇者がいなければならない。
• 同じパーティの勇者と戦士は仲良くなければならない。
• 同じパーティの戦士と僧侶は仲良くなければならない。
• 同じパーティの僧侶と魔法使いは仲良くなければならない。
• パーティには必ずしも 4 種のジョブがそろってなくても良い。ただし, 僧侶がいない場合は戦士, 魔法使いはいなければならない。
• パーティには戦士, 僧侶, 魔法使いがいなくても良いが, それぞれ Nw, Nc, Nm 個以下のパーティでそうでなければならない。

解法

見た目からしてマッチング -> 最大フローという流れが目に浮かびます。具体的には以下のようなグラフを作れば良いです。

汚くてすみません。
個人的に引っかかったのですが, Nw とかの辺を意識するのはすぐわかったんですが普通の辺に対してもバッファみたいのを付けないとその頂点からフローが 2 以上流れる可能性があるのを忘れてました。

あと頂点のラベル付けがめっちゃめんどくさいのである程度まとまりをつけて変数化すべきですね。

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
	int H, W, C, M, Nw, Nc, Nm;
	while (cin >> H >> W >> C >> M >> Nw >> Nc >> Nm) {
		if (H == -1) break;
		int s = H + 2 * (W + 1) + 2 * (C + 1) + 2 * (M + 1);
		int t = s + 1, V = t + 1;
		Dinic dinic(V);
		int w1 = H + W, w2 = w1 + W + 1;
		int c1 = w2 + C + 1, c2 = c1 + C + 1;
		int m1 = c2 + M + 1, m2 = m1 + M + 1;

		for (int i = 0; i < H; i++) {
			dinic.add_edge(s, i, 1);
			dinic.add_edge(i, w1, 1);
		}

		for (int i = 0; i < W; i++) {
			// 上 -> 下
			dinic.add_edge(H + i, w1 + 1 + i, 1);
			// 次のプールにつなげる
			dinic.add_edge(w1 + 1 + i, c1, 1);
		}
		dinic.add_edge(w1, w2, Nw);
		
		for (int i = 0; i < C; i++) {
			// 上 -> 下
			dinic.add_edge(w2 + 1 + i, c1 + 1 + i, 1);
			// 次のプールにつなげる
			dinic.add_edge(c1 + 1 + i, m1, 1);
			// 前のプールからつなげる
			dinic.add_edge(w2, w2 + 1 + i, 1);
		}
		dinic.add_edge(c1, c2, Nc);

		for (int i = 0; i < M; i++) {
			// 上 -> 下
			dinic.add_edge(c2 + 1 + i, m1 + 1 + i, 1);
			// 前のプールからつなげる
			dinic.add_edge(c2, c2 + 1 + i, 1);
			// t につなげる
			dinic.add_edge(m1 + 1 + i, t, 1);
		}
		dinic.add_edge(m1, m2, Nm);
		dinic.add_edge(m2, t, Nm);

		for (int i = 0; i < W; i++) {
			int N;
			cin >> N;
			for (int j = 0; j < N; j++) {
				int h;
				cin >> h; h--;
				dinic.add_edge(h, H + i, 1);
			}
		}
		for (int i = 0; i < C; i++) {
			int N;
			cin >> N;
			for (int j = 0; j < N; j++) {
				int w;
				cin >> w; w--;
				dinic.add_edge(w + H, w2 + 1 + i, 1);
			}
		}
		for (int i = 0; i < M; i++) {
			int N;
			cin >> N;
			for (int j = 0; j < N; j++) {
				int c;
				cin >> c; c--;
				dinic.add_edge(c1 + 1 + c, m1 + 1 + i, 1);
			}
		}
		cout << dinic.max_flow(s, t) << endl;
	}
    return 0;
}