TopCoder SRM 630 Div1 Easy: Egalitarianism3 (グラフ)
解法
ワーシャルフロイトで2点間の最短距離を出しておく。2点を選び、その2点を含む集合を求め、その最大値を返せば良い。
コード
import java.util.ArrayList; public class Egalitarianism3 { public int maxCities(int n, int[] a, int[] b, int[] len) { if (n <= 2) { return n; } final int INF = 500000; int[][] map = new int[n][n]; for (int i = 0; i < len.length; i++) { int x = a[i] - 1; int y = b[i] - 1; int l = len[i]; map[x][y] = l; map[y][x] = l; } for (int i = 0; i < map.length; i++) { for (int j = 0; j < map.length; j++) { if (map[i][j] == 0) { map[i][j] = INF; } } } for (int k = 0; k < map.length; k++) { for (int i = 0; i < map.length; i++) { for (int j = 0; j < map.length; j++) { map[i][j] = Math.min(map[i][j], map[i][k] + map[k][j]); } } } int max = 0; ArrayList<Integer> list = new ArrayList<>(); for (int i = 0; i < map.length; i++) { for (int j = i + 1; j < map.length; j++) { list.clear(); int d = map[i][j]; list.add(i); list.add(j); for (int k = j + 1; k < map.length; k++) { boolean joinable = true; for (Integer l : list) { if (map[k][l] != d) { joinable = false; break; } } if (joinable) { list.add(k); } } max = Math.max(max, list.size()); } } return max; } }