AOJ2168 Luigi's Tavern

問題リンク Luigi's Tavern

  • 概要

H人の勇者、W人の戦士、C人の僧侶、M人の魔法使いがいる。彼らを招いてパーティーを開きたい。パーティーが成立するための条件は以下の通り
・勇者は必ずいなければならない
・パーティーに参加している勇者と戦士は親しくなければならない
・パーティーに参加している戦士と僧侶は親しくなければならない
・パーティーに参加している僧侶と魔法使いは親しくなければならない
・パーティーには戦士、僧侶、魔法使いが参加することが望まれるが、戦士がいないパーティーは最大Nw個まで、僧侶がいないパーティーは最大Nc個まで、魔法使いがいないパーティーは最大Nm個まであってもよい
・僧侶がいないパーティーには、戦士と魔法使いが必ず参加しなければならない
入力には、H, W, C, M, Nw, Nc, Nmと、
各戦士について、親しい勇者リスト
各僧侶について、親しい戦士リスト
各魔法使いについて、親しい僧侶リスト
が与えられる。開くことができるパーティーの最大数を答えよ。
0 <= H, W, C, M, Nw, Nc, Nm <= 50

  • 解法

最大流問題となります。グラフは以下の図を見てニュアンスを感じとってください。

重みが書いていない辺は全て1です。
HiとWj, WiとCj, CiとMjは仲の良い人物同士であることを示しています。
W, C, Mの段の右側にあるノードは、各職業の人物を誘わない場合を示しています。誘わない場合の最大数(Nw, Nc, Nm)が辺の重みです。
僧侶がいない場合の特殊なパーティーに対応するために、WとC、CとMのノードは直接結んではいけないのです。
あとはこの最大流をFord-Fulkersonか何かで求めます。

  • ソース
import java.util.Arrays;
import java.util.Scanner;

//Luigi's Tavern
public class AOJ2168 {

	int augumentPath(int v, int t, int f, int[][] cap, boolean[] used){
		if(v==t)return f;
		used[v] = true;
		for(int i=0;i<cap[v].length;i++){
			if(cap[v][i]>0 && !used[i]){
				int d = augumentPath(i, t, Math.min(f, cap[v][i]), cap, used);
				if(d>0){
					cap[v][i] -= d;
					cap[i][v] += d;
					return d;
				}
			}
		}
		return 0;
	}
	
	int maxFlow(int s, int t, int[][] cap){
		int flow = 0;
		int n = cap.length;
		boolean[] used = new boolean[n];
		while(true){
			Arrays.fill(used, false);
			int f = augumentPath(s, t, Integer.MAX_VALUE, cap, used);
			if(f==0)return flow;
			flow += f;
		}
	}
	
	void run(){
		Scanner sc = new Scanner(System.in);
		for(;;){
			int h = sc.nextInt(), w = sc.nextInt(), c = sc.nextInt(), m = sc.nextInt(), nw = sc.nextInt(), nc = sc.nextInt(), nm = sc.nextInt();
			if(h<0)break;
			int n = h+w+c+m, NW = n, NC = n+1, NM = n+2, N = n+3, S = 2*N, T = 2*N+1;
			int[][] cap = new int[2*N+2][2*N+2];
			for(int i=0;i<n;i++)cap[i+N][i] = 1;
			cap[NW+N][NW] = nw;
			cap[NC+N][NC] = nc;
			cap[NM+N][NM] = nm;
			for(int i=0;i<h;i++){
				cap[S][i+N] = 1; cap[i][NW+N] = 1;
			}
			for(int i=0;i<w;i++){
				int k = sc.nextInt();
				while(k--!=0){
					int id = sc.nextInt()-1;
					cap[id][h+i+N] = 1;
				}
				cap[h+i][NC+N] = 1;
			}
			for(int i=0;i<c;i++){
				int k = sc.nextInt();
				while(k--!=0){
					int id = sc.nextInt()-1+h;
					cap[id][i+h+w+N] = 1;
				}
				cap[h+w+i][NM+N] = 1;
			}
			for(int i=0;i<m;i++){
				int k = sc.nextInt();
				while(k--!=0){
					int id = sc.nextInt()-1+h+w;
					cap[id][i+h+w+c+N] = 1;
				}
				cap[i+h+w+c][T] = 1;
			}
			for(int i=0;i<c;i++)cap[NW][i+h+w+N] = 1;
			for(int i=0;i<m;i++)cap[NC][i+h+w+c+N] = 1;
			cap[NM][T] = nm;
			System.out.println(maxFlow(S, T, cap));
		}
	}
	
	public static void main(String[] args) {
		new AOJ2168().run();
	}
}