Archive for the ‘Maxflow’ Category

UVA – 10092 – The Problem with the Problem Setter   Leave a comment


Direct maximum flow problem, need to be implemented using adjacency list.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class TheProblemWithTheProblemSetter {
	static class Edge {
		Edge dual;
		int s, t, cap;

		public Edge(int s, int t, int cap) {
			this.s = s;
			this.t = t;
			this.cap = cap;
		}
	}

	public static int maxflow(int s, int t, LinkedList<Edge>[] G) {
		Edge[] parent = new Edge[G.length];
		int[] flow = new int[G.length];
		int result = 0;
		while (bfs(s, t, G, flow, parent) != 0) {
			result += flow[t];
			augment(s, t, flow[t], parent);
		}
		return result;
	}

	public static void augment(int s, int t, int flow, Edge[] parent) {
		while (t != s) {
			parent[t].cap -= flow;
			parent[t].dual.cap += flow;
			t = parent[t].s;
		}
	}

	public static int bfs(int s, int t, LinkedList<Edge>[] G, int[] flow,
			Edge[] parent) {
		Queue<Integer> Q = new ArrayDeque<Integer>();
		Q.add(s);
		Arrays.fill(flow, 0);
		Arrays.fill(parent, null);
		flow[s] = Integer.MAX_VALUE;
		while (!Q.isEmpty()) {
			int n = Q.poll();
			if (n == t)
				return flow[t];
			for (Edge e : G[n]) {
				if (flow[e.t] == 0 && e.cap > 0) {
					flow[e.t] = Math.min(flow[n], e.cap);
					parent[e.t] = e;
					Q.add(e.t);
				}
			}
		}
		return 0;
	}

	public static void main(String[] args) throws Exception {
		InputReader in = new InputReader(System.in);
		while (true) {
			int c = in.nextInt();
			int p = in.nextInt();
			if (c == 0 && p == 0)
				break;
			LinkedList<Edge>[] G = new LinkedList[c + p + 2];
			for (int i = 0; i < G.length; i++) {
				G[i] = new LinkedList<Edge>();
			}
			int sum = 0;
			for (int i = 0; i < c; i++) {
				int w = in.nextInt();
				sum += w;
				Edge x = new Edge(0, i + 1, w);
				Edge y = new Edge(i + 1, 0, 0);
				x.dual = y;
				y.dual = x;
				G[0].add(x);
				G[i + 1].add(y);
			}
			for (int i = 0; i < p; i++) {
				int cnt = in.nextInt();
				for (int j = 0; j < cnt; j++) {
					int cat = in.nextInt();
					Edge x = new Edge(cat, c + i + 1, 1);
					Edge y = new Edge(c + i + 1, cat, 0);
					x.dual = y;
					y.dual = x;
					G[cat].add(x);
					G[c + i + 1].add(y);
				}
				Edge x = new Edge(c + i + 1, c + p + 1, 1);
				Edge y = new Edge(c + p + 1, c + i + 1, 0);
				x.dual = y;
				y.dual = x;
				G[c + i + 1].add(x);
				G[c + p + 1].add(y);
			}
			if (maxflow(0, p + c + 1, G) == sum) {
				System.out.println("1");
				for (int i = 1; i <= c; i++) {
					LinkedList<Integer> res = new LinkedList<Integer>();
					for (Edge e : G[i])
						if (e.cap == 0)
							res.add(e.t - c);
					StringBuilder out = new StringBuilder();
					for (int k : res)
						out.append(k + " ");
					if (out.length() > 0)
						out.deleteCharAt(out.length() - 1);
					System.out.println(out);
				}
			} else
				System.out.println("0");

		}
	}

	static class InputReader {
		private BufferedReader reader;
		private StringTokenizer tokenizer;

		public InputReader(InputStream stream) {
			reader = new BufferedReader(new InputStreamReader(stream));
			tokenizer = null;
		}

		public String next() {
			while (tokenizer == null || !tokenizer.hasMoreTokens()) {
				try {
					tokenizer = new StringTokenizer(reader.readLine());
				} catch (IOException e) {
					throw new RuntimeException(e);
				}
			}
			return tokenizer.nextToken();
		}

		public int nextInt() {
			return Integer.parseInt(next());
		}
	}

}

Advertisements

Posted October 27, 2012 by epicrado in Maxflow

UVA – 12159 – Gun Fight   Leave a comment


Maximum matching problem with little geometry, first split the towers having power into two sets then for each tower in the smaller set which can fight and beat a tower in the larger set add an edge and run maximum matching

#include <complex>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <iostream>
#include <math.h>
#include <stdio.h>
#include  <queue>
#include  <stack>
using namespace std;

typedef complex<long long> point;
#define EPS 1e-9
#define INF 1e9
#define X real()
#define Y imag()
#define polar(r,t) ((r)*exp(point(0,t)))
#define length(a) hypot((a).X,(a).Y)
#define angle(a) atan2(((a).Y),((a).X))
#define sqrdist(a) (((a)*(conj(a))).real())
#define dist(a) (sqrt(sqrdist((a))))
#define rotate(a,t) ((a)*(exp(point(0,(t)))))
#define rotateabout(a,t,b) ((rotate(((a)-(b)),(t)))+(b))
#define vec(a,b) ((b)-(a))
#define dot(a,b) ((conj(a)*(b)).real())
#define cross(a,b) ((conj(a)*(b)).imag())
#define reflect(v,M) (conj((v)/(M)) * (M))
#define ccw(a,b,c) (cross(vec((a),(b)),vec((a),(c)))>EPS)
#define collinear(a,b,c) (fabs(cross(vec((a),(b)),vec((a),(c))))<EPS)
#define cosRule(a,b,c) (((a)*(a) + (b)*(b) - (c)*(c))/(2*(a)*(b)))
#define sz(a) ((int)(a.size()))

int find(int i, int *p) {
	return p[i] = ((p[i] == i) ? i : find(p[i], p));
}
void merge(int a, int b, int * p) {
	p[find(a, p)] = find(b, p);
}

int res[315][315];
int p[315];
int set[315];
int x[315];
int y[315];
int power[315];
int count1[315];
int fl[315];

int bfs(int a, int b, int* p, int *flow, int res[][315], int n) {
	queue<int> q;
	for (int i = 0; i < n; i++) {
		flow[i] = 0;
		p[i] = -1;
	}
	q.push(a);
	p[a] = a;
	flow[a] = INF;
	while (sz(q) ) {
		int i = q.front();
		q.pop();
		for (int j = 0; j < n; j++)
			if (res[i][j] && p[j] == -1) {
				p[j] = i;
				flow[j] = min(res[i][j], flow[i]);
				q.push(j);
			}
	}
	return flow[b];
}
void augmentPath(int a, int b, int flow, int *p, int res[][315], int n) {
	int i = b;
	while (i != a) {
		res[p[i]][i] -= flow;
		res[i][p[i]] += flow;
		i = p[i];
	}
}
int maxFlow(int a, int b, int* p, int * flow, int res[][315], int n) {
	int x;
	int result = 0;
	while ((x = bfs(a, b, p, flow, res, n))) {
		augmentPath(a, b, x, p, res, n);
		result += x;
	}
	return result;
}

int main(int argc, char **argv) {
	int n;
	int cc = 1;
	while (1) {
		cin >> n;
		if (!n)
			break;
		for (int i = 0; i < n; i++)
			cin >> x[i] >> y[i] >> power[i];
		int a;
		int b;
		int r;
		cin >> a >> b >> r;
		a--;
		b--;
		point p1(x[a], y[a]);
		point q1(x[b], y[b]);
		for (int i = 0; i < n; count1[i] = 0, i++)
			set[i] = i;
		for (int i = 0; i < n; i++)
			for (int j = i + 1; j < n; j++)
				if (power[i] && power[j]
						&& ccw(p1,q1,point(x[i],y[i]))
								== ccw(p1,q1,point(x[j],y[j]))) {
					merge(i, j, set);
				}

		for (int i = 0; i < n + 2; i++)
			for (int j = 0; j < n + 2; j++)
				res[i][j] = 0;
		for (int i = 0; i < n; i++)
			if (power[i])
				count1[find(i, set)]++;
		int min = INF;
		int max = 0;
		for (int i = 0; i < n; i++) {
			if (power[i] && count1[i] < min && count1[i])
				min = count1[i];

			if (count1[i] > max && count1[i] && power[i])
				max = count1[i];
		}
		for (int i = 0; i < n; i++)
			if (power[i] && count1[find(i, set)] == min) {
				res[0][i + 1] = 1;
			} else if (power[i] && count1[find(i, set)] > min) {
				res[i + 1][n + 1] = 1;
			}
		for (int i = 0; i < n; i++)
			for (int j = 0; j < n; j++) {
				if (count1[find(i, set)] == min&& power[i] && power[j]
				&& ccw(p1,q1,point(x[i],y[i]))
				!= ccw(p1,q1,point(x[j],y[j]))) {if (sqrdist(vec(point(x[i],y[i]),point(x[j],y[j])))
						<= r * r && power[i] > power[j]) {
					res[i + 1][j + 1] = 1;
				}
			}

		}
		printf("Case %d: %d\n", cc++, maxFlow(0, n + 1, p, fl, res, n + 2));
	}
	return 0;
}

Posted August 21, 2012 by epicrado in Bipartite matching, Graphs, Maxflow

UVA – 10511 – Councilling   Leave a comment


Maxflow again.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Map.Entry;
import java.util.Set;

public class Counciling {
	public static int bfs(int s, int t, int[][] res, int[] parent,
			LinkedList<Integer>[] adlist) {
		Queue<Integer> Q = new LinkedList<Integer>();
		Q.add(s);
		Q.add(Integer.MAX_VALUE);
		while (!Q.isEmpty()) {
			int n = Q.poll();
			int flow = Q.poll();
			if (n == t)
				return flow;
			for (int j : adlist[n]) {
				if (res[n][j] > 0 && parent[j] == -1) {
					Q.add(j);
					Q.add(Math.min(flow, res[n][j]));
					parent[j] = n;
				}
			}
		}
		return 0;
	}

	public static void augmentPath(int s, int t, int flow, int[] parent,
			int[][] res) {
		int cur = t;
		while (cur != s) {
			res[parent[cur]][cur] -= flow;
			res[cur][parent[cur]] += flow;
			cur = parent[cur];
		}
	}

	public static int maxFlow(int s, int t, int[][] res) {
		LinkedList<Integer>[] adlist = new LinkedList[res.length];
		for (int i = 0; i < adlist.length; i++)
			adlist[i] = new LinkedList<Integer>();
		for (int i = 0; i < res.length; i++) {
			for (int j = 0; j < res.length; j++) {
				if (res[i][j] > 0) {
					adlist[i].add(j);
					if (res[j][i] == 0)
						adlist[j].add(i);
				}
			}
		}
		int[] parent = new int[res.length];
		Arrays.fill(parent, -1);
		int flow, maxflow = 0;
		while ((flow = bfs(s, t, res, parent, adlist)) != 0) {
			maxflow += flow;
			augmentPath(s, t, flow, parent, res);
			Arrays.fill(parent, -1);
		}
		return maxflow;
	}

	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		int tc = Integer.parseInt(in.readLine());
		in.readLine();// empty line
		while (tc-- > 0) {
			String s;
			LinkedList<String> input = new LinkedList<String>();
			HashMap<String, Integer> person = new HashMap<String, Integer>();
			HashMap<String, Integer> club = new HashMap<String, Integer>();
			HashMap<String, Integer> party = new HashMap<String, Integer>();
			int top = 1;
			while ((s = in.readLine()) != null && !s.equals("")
					&& !s.equals(" ")) {
				input.add(s);
				String[] arr = s.split(" ");
				person.put(arr[0], top++);
				if (arr.length > 1) {
					if (!party.containsKey(arr[1]))
						party.put(arr[1], top++);
				}
				for (int i = 2; i < arr.length; i++) {
					if (!club.containsKey(arr[i]))
						club.put(arr[i], top++);
				}
			}
			int[][] res = new int[top + 1][top + 1];
			for (String i : input) {
				String[] arr = i.split(" ");
				if (arr.length > 1) {
					res[person.get(arr[0])][party.get(arr[1])] = 1;
					for (int j = 2; j < arr.length; j++) {
						res[club.get(arr[j])][person.get(arr[0])] = 1;
					}
				}
			}
			int seats = (club.size() - 1) / 2;
			Set<Entry<String, Integer>> S = club.entrySet();
			for (Entry<String, Integer> E : S) {
				res[0][E.getValue()] = 1;
			}
			S = party.entrySet();
			for (Entry<String, Integer> E : S) {
				res[E.getValue()][top] = seats;
			}
			HashMap<Integer, String> mapBack = new HashMap<Integer, String>();
			S = person.entrySet();
			for (Entry<String, Integer> E : S) {
				mapBack.put(E.getValue(), E.getKey());
			}
			int flow = maxFlow(0, top, res);
			if (flow != club.size()) {
				System.out.println("Impossible.");
			} else {
				S = club.entrySet();
				for (Entry<String, Integer> E : S) {
					int cclub = E.getValue();
					for (int i = 0; i < top; i++) {
						if (res[i][cclub] == 1) {
							System.out.println(mapBack.get(i) + " "
									+ E.getKey());
						}
					}
				}
			}
			if (tc != 0)
				System.out.println();
		}
	}
}

Posted June 26, 2012 by epicrado in Maxflow

UVA – 10779 – Collectors Problem   Leave a comment


Maxflow the tricky part is to build the network graph.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class TheCollectorsProblem {
	public static int bfs(int s, int t, int[][] res, int[] parent) {
		Queue<Integer> Q = new LinkedList<Integer>();
		Q.add(s);
		Q.add(Integer.MAX_VALUE);
		while (!Q.isEmpty()) {
			int n = Q.poll();
			int flow = Q.poll();
			if (n == t)
				return flow;
			for (int j = 0; j < res[n].length; j++) {
				if (res[n][j] != 0 && parent[j] == -1) {
					Q.add(j);
					Q.add(Math.min(flow, res[n][j]));
					parent[j] = n;
				}
			}
		}
		return 0;
	}

	public static void augmentPath(int s, int t, int flow, int[] parent,
			int[][] res) {
		int cur = t;
		while (cur != s) {
			res[parent[cur]][cur] -= flow;
			res[cur][parent[cur]] += flow;
			cur = parent[cur];
		}
	}

	public static int maxFlow(int s, int t, int[][] res) {
		int[] parent = new int[res.length];
		Arrays.fill(parent, -1);
		int flow, maxflow = 0;
		while ((flow = bfs(s, t, res, parent)) != 0) {
			maxflow += flow;
			augmentPath(s, t, flow, parent, res);
			Arrays.fill(parent, -1);
		}
		return maxflow;
	}

	public static void main(String[] args) throws Exception {
		InputReader in = new InputReader(System.in);
		int tc = in.nextInt();
		for (int cc = 1; cc <= tc; cc++) {
			int n = in.nextInt();
			int m = in.nextInt();
			int[][] g = new int[n + m + 1][n + m + 1];
			for (int i = 0; i < n; i++) {
				int[] count = new int[m];
				int k = in.nextInt();
				for (int j = 0; j < k; j++)
					count[in.nextInt() - 1]++;
				if (i == 0) {
					for (int j = 0; j < count.length; j++) {
						g[0][j + 1] = count[j];
					}
				} else {
					int f = m + i;
					for (int j = 0; j < count.length; j++) {
						if (count[j] == 0)
							g[j + 1][f] = 1;
						if (count[j] > 1)
							g[f][j + 1] = count[j] - 1;
					}
				}
			}
			for (int i = 1; i <= m; i++)
				g[i][n + m] = 1;
			System.out.printf("Case #%d: %d\n", cc, maxFlow(0, n + m, g));
		}
	}

	static class InputReader {
		private BufferedReader reader;
		private StringTokenizer tokenizer;

		public InputReader(InputStream stream) {
			reader = new BufferedReader(new InputStreamReader(stream));
			tokenizer = null;
		}

		public String next() {
			while (tokenizer == null || !tokenizer.hasMoreTokens()) {
				try {
					tokenizer = new StringTokenizer(reader.readLine());
				} catch (IOException e) {
					throw new RuntimeException(e);
				}
			}
			return tokenizer.nextToken();
		}

		public int nextInt() {
			return Integer.parseInt(next());
		}
	}
}

Posted June 26, 2012 by epicrado in Maxflow

UVA – 753 – A Plug for UNIX   Leave a comment


Maxflow problem create nodes as types of sockets, connect source by those nodes which are needed by some device, socket’s nodes which are available by sink finally connect sockets (nodes) which exist in some adapter by each other using high weight (possibly something larger than 100 or so i used 1m) as there’s infinite supply of adapters.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class APlugForUnix {
	public static int bfs(int s, int t, int[][] res, int[] parent) {
		Queue<Integer> Q = new LinkedList<Integer>();
		Q.add(s);
		Q.add(Integer.MAX_VALUE);
		while (!Q.isEmpty()) {
			int n = Q.poll();
			int flow = Q.poll();
			if (n == t)
				return flow;
			for (int j = 0; j < res[n].length; j++) {
				if (res[n][j] != 0 && parent[j] == -1) {
					Q.add(j);
					Q.add(Math.min(flow, res[n][j]));
					parent[j] = n;
				}
			}
		}
		return 0;
	}

	public static void augmentPath(int s, int t, int flow, int[] parent,
			int[][] res) {
		int cur = t;
		while (cur != s) {
			res[parent[cur]][cur] -= flow;
			res[cur][parent[cur]] += flow;
			cur = parent[cur];
		}
	}

	public static int maxFlow(int s, int t, int[][] res) {
		int[] parent = new int[res.length];
		Arrays.fill(parent, -1);
		int flow, maxflow = 0;
		while ((flow = bfs(s, t, res, parent)) != 0) {
			maxflow += flow;
			augmentPath(s, t, flow, parent, res);
			Arrays.fill(parent, -1);
		}
		return maxflow;
	}

	public static void main(String[] args) throws Exception {
		InputReader in = new InputReader(System.in);
		int tc = in.nextInt();
		while (tc-- > 0) {
			HashMap<String, Integer> index = new HashMap<String, Integer>();
			int top = 1;
			int cnt1 = in.nextInt();
			ArrayList<Integer> out = new ArrayList<Integer>();
			ArrayList<Integer> inp = new ArrayList<Integer>();
			for (int i = 0; i < cnt1; i++) {
				String s = in.next();
				if (!index.containsKey(s))
					index.put(s, top++);
				out.add(index.get(s));
			}
			int cnt2 = in.nextInt();
			for (int i = 0; i < cnt2; i++) {
				String crap = in.next();// useless stuff 😀 😀
				String s = in.next();
				if (!index.containsKey(s))
					index.put(s, top++);
				inp.add(index.get(s));
			}
			int cnt3 = in.nextInt();
			int[] f = new int[cnt3];
			int[] t = new int[cnt3];
			for (int i = 0; i < cnt3; i++) {
				String s1 = in.next();
				if (!index.containsKey(s1))
					index.put(s1, top++);
				String s2 = in.next();
				if (!index.containsKey(s2))
					index.put(s2, top++);
				f[i] = index.get(s1);
				t[i] = index.get(s2);
			}
			int[][] res = new int[top + 1][top + 1];
			for (int i = 0; i < inp.size(); i++)
				res[0][inp.get(i)]++;
			for (int i = 0; i < out.size(); i++)
				res[out.get(i)][top]++;
			for (int i = 0; i < cnt3; i++)
				res[f[i]][t[i]] += 1 << 20;// infinity supply of adapters
			System.out.println(cnt2 - maxFlow(0, top, res));
			if (tc != 0)
				System.out.println();
		}
	}

	static class InputReader {
		private BufferedReader reader;
		private StringTokenizer tokenizer;

		public InputReader(InputStream stream) {
			reader = new BufferedReader(new InputStreamReader(stream));
			tokenizer = null;
		}

		public String next() {
			while (tokenizer == null || !tokenizer.hasMoreTokens()) {
				try {
					tokenizer = new StringTokenizer(reader.readLine());
				} catch (IOException e) {
					throw new RuntimeException(e);
				}
			}
			return tokenizer.nextToken();
		}

		public int nextInt() {
			return Integer.parseInt(next());
		}
	}
}

Posted June 26, 2012 by epicrado in Maxflow

UVA – 10746 – Crime Wave – The Sequel   2 comments


Min cost bipartite matching done with Edmonds karp modified to use bellman ford instead of bfs and some other modifications to get the min cost max flow

import java.util.Arrays;
import java.util.Scanner;

public class CrimeWave {
	static int INF = 1 << 29;

	public static double augmentPath(double[][] weight, int[][] res,
			int[] parent, int s, int t, int f) {
		int i = t;
		double cost = 0;
		while (parent[i] != -1) {
			res[parent[i]][i] -= f;
			cost += f * weight[parent[i]][i];
			res[i][parent[i]] += f;
			i = parent[i];
		}
		return cost;
	}

	public static int bf(double[][] weight, int[][] res, int[] parent, int s,
			int t) {
		double[] d = new double[weight.length];
		int[] f = new int[weight.length];
		Arrays.fill(f, 0);
		Arrays.fill(d, INF);
		d[s] = 0;
		f[s] = INF;
		Arrays.fill(parent, -1);
		for (int c = 0; c < weight.length - 1; c++) {
			for (int i = 0; i < weight.length; i++)
				for (int j = 0; j < weight.length; j++) {
					if (d[i] + weight[i][j] < d[j] && res[i][j] > 0) {
						d[j] = d[i] + weight[i][j];
						f[j] = Math.min(f[i], res[i][j]);
						parent[j] = i;
					}
				}
		}
		return f[t];
	}

	public static double minCostMaxFlow(int flow, double[][] weight,
			int[][] res, int s, int t) {
		for (int i = 0; i < res.length; i++)
			for (int j = 0; j < res.length; j++)
				if (res[i][j] != 0)
					weight[j][i] = -weight[i][j];
		int[] parent = new int[weight.length];
		double cost = 0;
		while (flow != 0) {
			int current = bf(weight, res, parent, s, t);
			if (current == 0)
				return INF;
			cost += augmentPath(weight, res, parent, s, t,
					Math.min(current, flow));
			flow -= current;
		}
		return cost;
	}

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		while (true) {
			int n = in.nextInt();
			int m = in.nextInt();
			if (n == 0 && m == 0)
				break;
			double[][] w = new double[n + m + 2][n + m + 2];
			int[][] res = new int[n + m + 2][n + m + 2];
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < m; j++) {
					w[j + 1][m + i + 1] = in.nextDouble();
					res[j + 1][m + i + 1] = 1;
					w[0][j + 1] = 0;
					res[0][j + 1] = 1;
				}
				w[m + i + 1][w.length - 1] = 0;
				res[m + i + 1][w.length - 1] = 1;
			}
			System.out.printf("%.2f\n",
					minCostMaxFlow(n, w, res, 0, w.length - 1) / n + 1e-6);
		}
	}
}

Posted June 16, 2012 by epicrado in Maxflow

UVA – 11262 – Weird Fence   Leave a comment


Basic idea is binary search on the max allowed distance between two poles and build a graph using this distance, and do maximum matching to see where the binary search should go.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class WeirdFence {
	public static int bfs(int s, int t, int[][] res, int[] parent) {
		Queue<Integer> Q = new LinkedList<Integer>();
		Q.add(s);
		Q.add(Integer.MAX_VALUE);
		while (!Q.isEmpty()) {
			int n = Q.poll();
			int flow = Q.poll();
			if (n == t)
				return flow;
			for (int j = 0; j < res[n].length; j++) {
				if (res[n][j] != 0 && parent[j] == -1) {
					Q.add(j);
					Q.add(Math.min(flow, res[n][j]));
					parent[j] = n;
				}
			}
		}
		return 0;
	}

	public static void augmentPath(int s, int t, int flow, int[] parent,
			int[][] res) {
		int cur = t;
		while (cur != s) {
			res[parent[cur]][cur] -= flow;
			res[cur][parent[cur]] += flow;
			cur = parent[cur];
		}
	}

	public static int maxFlow(int s, int t, int[][] res) {
		int[] parent = new int[res.length];
		Arrays.fill(parent, -1);
		int flow, maxflow = 0;
		while ((flow = bfs(s, t, res, parent)) != 0) {
			maxflow += flow;
			augmentPath(s, t, flow, parent, res);
			Arrays.fill(parent, -1);
		}
		return maxflow;
	}

	public static void main(String[] args) throws Exception {
		InputReader in = new InputReader(System.in);
		int tc = in.nextInt();
		while (tc-- > 0) {
			int n = in.nextInt();
			int k = in.nextInt();
			int[] x = new int[n];
			int[] y = new int[n];
			boolean[] col = new boolean[n];
			for (int i = 0; i < n; i++) {
				x[i] = in.nextInt();
				y[i] = in.nextInt();
				String s = in.next();
				col[i] = s.equals("red");
			}

			int l = 0;
			int h = 3000;
			boolean ok = false;
			while (h > l) {
				int mid = (l + h) / 2;
				int[][] g = new int[n + 2][n + 2];
				for (int i = 0; i < n; i++) {
					if (col[i])
						g[0][i + 1] = 1;
					else
						g[i + 1][n+1] = 1;
				}
				for (int i = 0; i < n; i++) {
					for (int j = 0; j < n; j++) {
						if (col[i]
								&& !col[j]
								&& (x[i] - x[j]) * (x[i] - x[j])
										+ (y[i] - y[j]) * (y[i] - y[j]) <= mid
										* mid) {
							g[i + 1][j + 1] = 1;
						}
					}
				}
				int max = maxFlow(0, n+1, g);
				if (max >= k) {
					h = mid;
					ok = true;
				} else
					l = mid + 1;
			}
			if (ok)
				System.out.println(h);
			else
				System.out.println("Impossible");
		}
	}

	static class InputReader {
		private BufferedReader reader;
		private StringTokenizer tokenizer;

		public InputReader(InputStream stream) {
			reader = new BufferedReader(new InputStreamReader(stream));
			tokenizer = null;
		}

		public String next() {
			while (tokenizer == null || !tokenizer.hasMoreTokens()) {
				try {
					tokenizer = new StringTokenizer(reader.readLine());
				} catch (IOException e) {
					throw new RuntimeException(e);
				}
			}
			return tokenizer.nextToken();
		}

		public int nextInt() {
			return Integer.parseInt(next());
		}
	}
}

Posted June 13, 2012 by epicrado in Binary search, Graphs, Maxflow