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(); } }