Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2011-05-28SRM300台を練習していく part5

SRM 303 Knights

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

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

蟻本を参考に最大流のオレオレライブラリを作って解いてみた。

でもまだ最小カットと最大流が等しくなることが直感的に理解できないんだよなぁ。


import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

public class Knights {
	public class Edge {
		int to;
		int cap;
		int rev;
		public Edge(int _to, int _cap, int _rev) {
			to = _to;
			cap = _cap;
			rev = _rev;
		}
	}
	public Map<Integer, List<Edge>> graph = new HashMap<Integer, List<Edge>>();
	public boolean[] used;
	public void init(int size) {
		for (int i = 0 ; i < size ; i++) {
			graph.put(i, new ArrayList<Edge>());
		}
		used = new boolean[size];
	}
	public void edge(int from, int to, int cap) {
		graph.get(from).add(new Edge(to, cap, graph.get(to).size()));
		graph.get(to).add(new Edge(from, 0, graph.get(from).size() - 1));
	}
	public int dfs(int v, int t, int f) {
		if (v == t) return f;
		used[v] = true;
		for (int i = 0 ; i < graph.get(v).size() ; i++) {
			Edge e = graph.get(v).get(i);
			if (!used[e.to] && e.cap > 0) {
				int d = dfs(e.to, t, Math.min(f, e.cap));
				if (d > 0) {
					e.cap -= d;
					graph.get(e.to).get(e.rev).cap += d;
					return d;
				}
			}
		}
		return 0;
	}
	public int max_flow(int s, int t) {
		int flow = 0;
		while (true) {
			used = new boolean[graph.size()];
			int f = dfs(s, t, Integer.MAX_VALUE);
			if (f == 0) {
				break;
			}
			flow += f;
		}
		return flow;
	}


	public int[] kx = {-2, -1, 1, 2, -2, -1, 1, 2};

	public int[] ky = {-1, -2, -2, -1, 1, 2, 2, 1};

	public int makeFriendly(int N, String[] pos) {
		int[][] field = new int[N][N];
		int knights = 0;
		for (String p : pos) {
			for (String kp : p.split(" ")) {
				int r = kp.charAt(0) - 'A';
				int c = Integer.valueOf(kp.substring(1)) - 1;
				knights++;
				field[r][c] = knights;
			}
		}


		init(knights + 2);
		Set<Integer> from = new HashSet<Integer>();
		Set<Integer> to = new HashSet<Integer>();
		for (int i = 0 ; i < N ; i++) {
			for (int j = 0 ; j < N ; j++) {
				if (field[i][j] > 0) {
					if ((i + j) % 2 == 1) {
						int s = field[i][j] - 1;
						from.add(s);
						for (int d = 0 ; d < 8 ; d++) {
							int dx = j + kx[d];
							int dy = i + ky[d];
							try {
								if (field[dy][dx] > 0) {
									int m = field[dy][dx] - 1;
									to.add(m);
									edge(s, m, 1);
								}
							} catch (Exception e) {
							}
						}
					}
				}
			}
		}

		int source = knights;
		int sink = knights + 1;
		for (int s : from) {
			edge(source, s, 1);
		}
		for (int m : to) {
			edge(m, sink, 1);
		}
		return max_flow(source, sink);
	}
}