ACM ICPC East-Siberian Subregional Contest 2011. Problem F. Dinica (Public copy)

Main.java

import java.io.*;
import java.util.*;
import static java.lang.Math.*;

public class Main {

	BufferedReader in;
	StringTokenizer st;
	PrintWriter out;

	class Graph {
		Edge[] g;
		int n;

		public Graph(int n) {
			this.n = n;
			g = new Edge[n];
		}

		void add(int v, Edge e) {
			if (g[v] == null)
				g[v] = e;
			else {
				e.next = g[v];
				g[v] = e;
			}
		}

		void addEdge(int v, int u, int cap) {
			Edge e1 = new Edge(v, u, 0, cap);
			Edge e2 = new Edge(u, v, 0, 0);
			e1.rev = e2;
			e2.rev = e1;
			add(v, e1);
			add(u, e2);
		}

		int maxFlow() {
			int ret = 0;
			while (true) {
				bfs(0);
				if (d[n - 1] >= INF)
					break;
				for (int i = 0; i < n; ++i)
					ptr[i] = g[i];
				int a = dfs(0, INF);
				ret += a;
				if (a == 0)
					break;
				while (true) {
					a = dfs(0, INF);
					if (a == 0)
						break;
					ret += a;
				}
			}
			return ret;
		}

		final int INF = 1 << 29;

		int dfs(int v, int flow) {
			if (v == n - 1)
				return flow;
			for (; ptr[v] != null; ptr[v] = ptr[v].next) {
				Edge edge = ptr[v];
				int u = edge.u;
				if (d[u] == d[v] + 1) {
					int a = min(flow, edge.cap - edge.flow);
					a = dfs(u, a);
					if (a > 0) {
						edge.flow += a;
						edge.rev.flow -= a;
						return a;
					}
				}
			}
			return 0;
		}

		void bfs(int v) {
			Arrays.fill(d, INF);
			d[v] = 0;
			b = e = 0;
			for (q[e++] = v; b < e; ++b) {
				v = q[b];
				for (Edge edge = g[v]; edge != null; edge = edge.next) {
					int u = edge.u;
					if (edge.cap - edge.flow > 0) {
						if (d[u] > d[v] + 1) {
							d[u] = d[v] + 1;
							q[e++] = u;
						}
					}
				}
			}
		}
	}

	int[] d;
	int[] q = new int[1000000];
	Edge[] ptr = new Edge[100000];
	int b, e;

	static class Edge {
		int v, u, flow, cap;
		Edge rev;
		Edge next;

		public Edge(int v, int u, int flow, int cap) {
			super();
			this.v = v;
			this.u = u;
			this.flow = flow;
			this.cap = cap;
		}

	}

	static class Pair {
		int x, y;

		public Pair(int x, int y) {
			super();
			this.x = x;
			this.y = y;
		}

		long dist(Pair p) {
			return (long) (x - p.x) * (long) (x - p.x) + (long) (y - p.y)
					* (long) (y - p.y);
		}
	}

	void solve() throws IOException {
		for (int t = ni(); t > 0; --t) {
			int s = ni();
			int n = ni();
			int b = ni();
			long r = ni();
			r *= r;
			Pair[] v1 = new Pair[s];
			Pair[] v2 = new Pair[n];
			for (int i = 0; i < s; ++i)
				v1[i] = new Pair(ni(), ni());
			for (int i = 0; i < n; ++i)
				v2[i] = new Pair(ni(), ni());
			Graph g = new Graph(n + s + 2);
			for (int i = 0; i < s; ++i)
				for (int j = 0; j < n; ++j) {
					long d = v1[i].dist(v2[j]);
					if (d <= r) {
						g.addEdge(i + 1, j + s + 1, 1);
					}
				}
			for (int i = 1; i <= s; ++i)
				g.addEdge(0, i, b);
			for (int i = 1; i <= n; ++i)
				g.addEdge(i + s, g.n - 1, 1);
			d = new int[g.n];
			int ret = g.maxFlow();
			out.println(ret);
		}
	}

	public Main() throws IOException {
		gen();
		Locale.setDefault(Locale.US);
		in = new BufferedReader(new FileReader("input.txt"));
		out = new PrintWriter("output.txt");
		solve();
		in.close();
		out.close();
	}

	void gen() throws FileNotFoundException {
		PrintWriter out = new PrintWriter("test.txt");
		out.println("1\n100 100 25 40000");
		Random rnd = new Random();
		for (int i = 0; i < 100; ++i) {
			int x = rnd.nextInt(20000);
			int y = rnd.nextInt(20000);
			out.println(x + " " + y);
		}
		for (int i = 0; i < 100; ++i) {
			int x = rnd.nextInt(20000);
			int y = rnd.nextInt(20000);
			out.println(x + " " + y);
		}
		out.close();
	}

	String ns() throws IOException {
		while (st == null || !st.hasMoreTokens())
			st = new StringTokenizer(in.readLine());
		return st.nextToken();
	}

	int ni() throws IOException {
		return Integer.valueOf(ns());
	}

	double nd() throws IOException {
		return Double.valueOf(ns());
	}

	long nl() throws IOException {
		return Long.valueOf(ns());
	}

	public static void main(String[] args) throws IOException {
		new Main();
	}
}