Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2011-05-30SRM300台を練習していく part6

SRM 312 AntarcticaPolice

|  SRM 312 AntarcticaPolice - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 312 AntarcticaPolice - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=6501

各町から町へ(別の町を経由しても)到達できるかどうかはワーシャルフロイド法を使うと簡単に調べられる。

グラフを強連結成分分解して考える。詳しくはeditorial参照

http://www.topcoder.com/tc?module=Static&d1=match_editorials&d2=srm312


import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

public class AntarcticaPolice {

	public double minAverageCost(int[] costs, String[] roads) {
		int n = costs.length;
		boolean[][] reachable = new boolean[n][n];
		for (int i = 0 ; i < n ; i++) {
			reachable[i][i] = true;
			for (int j = 0 ; j < n ; j++) {
				if (roads[i].charAt(j) == 'Y') {
					reachable[i][j] = true;
				}
			}
		}
		for (int k = 0 ; k < n ; k++) {
			for (int i = 0 ; i < n ; i++) {
				for (int j = 0 ; j < n ; j++) {
					if (reachable[i][k] && reachable[k][j]) {
						reachable[i][j] = true;
					}
				}
			}
		}

		int[] group = new int[n];
		int[] groupCost = new int[n];
		int[] groupCostIndex = new int[n];
		int gnum = 0;
		for (int i = 0 ; i < n ; i++) {
			group[i] = -1;
			groupCost[i] = -1;
		}
		for (int i = 0 ; i < n ; i++) {
			if (group[i] != -1) {
				continue;
			}
			group[i] = gnum;
			groupCost[gnum] = costs[i];
			groupCostIndex[gnum] = i;
			for (int j = i + 1 ; j < n ; j++) {
				if (reachable[i][j] && reachable[j][i]) {
					if (costs[j] < groupCost[gnum]) {
						groupCost[gnum] = costs[j];
						groupCostIndex[gnum] = j;
					}
					group[j] = gnum;
				}
			}
			gnum++;
		}

		int total = 0;
		int num = 0;
		for (int g = 0 ; g < gnum ; g++) {
			boolean iscon = false;
			for (int i = 0 ; i < n ; i++) {
				if (group[i] == g) {
					continue;
				}
				for (int j = 0 ; j < n ; j++) {
					if (group[j] != g) {
						continue;
					}
					if (reachable[i][j]) {
						iscon = true;
						break;
					}
				}
				if (iscon) {
					break;
				}
			}
			if (!iscon) {
				total += groupCost[g];
				num++;
				costs[groupCostIndex[g]] = 999999;
			}
		}

		java.util.Arrays.sort(costs);
		for (int i = 0 ; i < n ; i++) {
			double now = (double) total / num;
			if ((double)(total + costs[i]) / (num + 1) < now) {
				total += costs[i];
				num++;
			}
		}
		return (double) total / num;
	}
}