AOJ2076 Flame of Nucleus - nanikakaのAOJ航海日誌

概要

N個のドームと、M本の双方向の道がある。ドームにはそれぞれPi人の人と、Ki人収容可能なシェルターがある。M本の道はドームiとドームjを結んで通行にD日の時間がかかる。
L日後に核が落とされる。L日目より早くシェルターに逃げ込んだ人は助かることができる(L日目ちょうどにシェルターに入っても助からない)。このとき、助かることができる最大人数を答えよ。
ドームiとドームjを結ぶ道は高々1つと仮定してよい。
1 <= N <= 100
0 <= M
1 <= L <= 10000
1 <= Di <= 10000
0 <= Pi <= 10^6
0 <= Ki <= 10^6

解法

最大流問題となります。
まずは、ドームiとドームjの全ドーム間の最短距離をワーシャルフロイド法等で求めておきます。iとjの最短距離がLよりちいさいならば、ドームiの人はドームjのシェルターまで移動可能と分かります。
最大流についてです。
頂点は2*N + 2個で内訳は、[各ドームについての頂点が2個ずつ]と[ソース]と[シンク]の頂点です。各ドームについての頂点はAi, Biと区別して表すことにします。
まずソースからAiに向けて、容量Piの辺を引きます。ドームにいる人の初期人数を表しています。
Biからシンクに向けて、容量Kiの辺を引きます。シェルターの収容制限を表しています。
次に最短距離がL未満であるようなドームiとドームjについて、AiからBjへ容量Piの辺を引きます。人がiのドームからjのドームへ移動することを表しています。
あとはこのグラフの最大フローを求めて答えとします。自分はFord-Fulkersonを使っています。少し遅いみたいですけど通りました。

ソース

import java.util.Arrays;
import java.util.Scanner;

//Flame of Nucleus
public class AOJ2076 {

	int INF = 1<<29;
	
	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);
		while(sc.hasNext()){
			int n = sc.nextInt(), m = sc.nextInt(), L = sc.nextInt();
			int[][] wf = new int[n+1][n+1];
			for(int[]a:wf)Arrays.fill(a, INF);
			for(int i=1;i<=n;i++)wf[i][i]=0;
			while(m--!=0){
				int s = sc.nextInt(), t = sc.nextInt(), c = sc.nextInt();
				wf[s][t]=wf[t][s]=c;
			}
			for(int k=1;k<=n;k++)for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)wf[i][j]=Math.min(wf[i][j], wf[i][k]+wf[k][j]);
			int[] p = new int[n+1], k = new int[n+1];
			for(int i=1;i<=n;i++)p[i]=sc.nextInt();
			for(int i=1;i<=n;i++)k[i]=sc.nextInt();
			int[][] cap = new int[n*2+2][n*2+2];
			for(int i=1;i<=n;i++)cap[0][i]=p[i];
			for(int i=1;i<=n;i++)cap[n+i][2*n+1]=k[i];
			for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(wf[i][j]<L)cap[i][n+j]=p[i];
			System.out.println(maxFlow(0, 2*n+1, cap));
		}
	}
	
	public static void main(String[] args) {
		new AOJ2076().run();
	}
}