SRM 477 Div1 Medium: PeopleYouMayKnow
問題
友人関係friendsと人の番号person1,person2が与えられる
friendsはN文字の文字列を値とするN要素配列で、i番目要素のj番目文字が'Y'のときはiとjが友人、'N'のときは友人でない。
あるAとBを決めた時に、AがBの友人であるときBはAの友人であるが、AとCが友人でCとBが友人のときにAとBが友人であるとは限らない。
AとBが友人のとき、AとBは1-friendsだと呼ぶ。また、においてAとCがn-friendsのときCとBが友人であるようなCが存在すれば、AとBは(n+1)-friendsである。AとBがn-friendのとき、AとBは(n+1)-friendsでもあるとする。
person1とperson2が3-friendsでないようにするためには最小で何人取り除けばよいかを求めよ。
制約
解法
最大フロー最小カット
person1,person2の両方と友人である人をまず取り除く。
その後、新しくフローネットワークを作ってsourceをperson1,sinkをperson2とした最大フローを求める。
はじめに取り除いた数と最大フローの和が求めるべき解になる。
public int maximalScore(String[] friends, int person1, int person2) { int n = friends.length; char[][] link = new char[n][]; for (int i=0; i<n; i++) link[i] = friends[i].toCharArray(); int cnt = 0; for (int i=0; i<n; i++) { if (link[i][person1] == 'Y' && link[i][person2] == 'Y') { cnt++; for (int j=0; j<n; j++) { link[i][j] = link[j][i] = 'N'; } } } DirectedGraph g = new DirectedGraph(n); int[] level = new int[n]; for (int i=0; i<n; i++) { if (i == person1) level[i] = 1; else if (link[person1][i] == 'Y') level[i] = 2; else if (link[person2][i] == 'Y') level[i] = 3; else if (i == person2) level[i] = 4; } for (int i=0; i<n; i++) { for (int j=0; j<n; j++) { if (link[i][j] == 'Y' && level[i] != 0 && level[j] != 0 && level[i] < level[j]) { g.addLink(i,j,1); } } } return requireMaxFlow(g,person1,person2) + cnt; } class DirectedGraph { public static final int INF = Integer.MAX_VALUE/2; public final int n; private ArrayList<ArrayList<int[]>> adjlist; public DirectedGraph(int n) { this.n = n; this.adjlist = new ArrayList<ArrayList<int[]>>(); for (int i=0; i<n; i++) adjlist.add(new ArrayList<int[]>()); } public void addLink(int from, int to) { addLink(from,to,0); } public void addLink(int from, int to, int c) { adjlist.get(from).add(new int[]{to,c}); } public ArrayList<int[]> get(int v) { return adjlist.get(v); } public String toString() { StringBuilder res = new StringBuilder(); for (int i=0; i<n; i++) { res.append(i).append(" ").append(Arrays.deepToString(adjlist.get(i).toArray())).append("\n"); } return res.substring(0,res.length()-1); } } static int requireMaxFlow(DirectedGraph g, int source, int sink) { int n = g.n; int[] cnt = new int[n]; for (int i=0; i<n; i++) for (int[] link : g.get(i)) cnt[link[0]]++; int[][] rev = new int[n][]; for (int i=0; i<n; i++) rev[i] = new int[cnt[i]]; for (int i=n-1; i>=0; i--) for (int[] link : g.get(i)) rev[link[0]][--cnt[link[0]]] = i; int[][] flow = new int[n][n]; int[] level = new int[n]; int[] path = new int[n]; int res = 0; while (true) { Arrays.fill(level,-1); path[0] = source; int ptr = 1; level[source] = 0; for (int i=0; i<ptr; i++) { int cur = path[i]; for (int[] link : g.get(cur)) { int next = link[0], cap = link[1]; if (level[next] == -1 && cap - flow[cur][next] > 0) { path[ptr++] = next; level[next] = level[cur] + 1; } } for (int next : rev[cur]) { if (level[next] == -1 && -flow[cur][next] > 0) { path[ptr++] = next; level[next] = level[cur] + 1; } } } if (level[sink] == -1) break; int f = 0; while ((f = dfsMaxFlow(g,level,rev,flow,source,sink,Integer.MAX_VALUE/2)) > 0) res += f; } return res; }