Archive for the ‘Bipartite matching’ Category

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 – 11138 – Nuts and Bolts   Leave a comment


import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class NutsAndBolts {
	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) {
		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());
		int cc = 1;
		StringBuilder out = new StringBuilder();
		while (tc-- > 0) {
			StringTokenizer st1 = new StringTokenizer(in.readLine(), " ");
			int n = Integer.parseInt(st1.nextToken());
			int b = Integer.parseInt(st1.nextToken());
			int[][] res = new int[n + b + 2][n + b + 2];
			LinkedList<Integer>[] adlist = new LinkedList[n + b + 2];
			for (int i = 0; i < adlist.length; i++)
				adlist[i] = new LinkedList<Integer>();
			for (int i = 1; i <= n; i++) {
				StringTokenizer st2 = new StringTokenizer(in.readLine(), " ");
				for (int j = 1; j <= b; j++) {
					res[i][n + j] = Integer.parseInt(st2.nextToken());
					if (res[i][n + j] == 1) {
						adlist[i].add(n + j);
						adlist[n + j].add(i);
					}
				}
			}
			for (int i = 1; i <= n; i++) {
				res[0][i] = 1;
				adlist[0].add(i);
				adlist[i].add(0);
			}
			for (int j = 1; j <= b; j++) {
				res[n + j][n + b + 1] = 1;
				adlist[n + j].add(n + b + 1);
				adlist[n + b + 1].add(n + j);
			}
			out.append("Case " + (cc++) + ": a maximum of "
					+ (maxFlow(0, res.length - 1, res, adlist))
					+ " nuts and bolts can be fitted together\n");
		}
		System.out.print(out);
	}
}

Posted February 2, 2012 by epicrado in Bipartite matching

UVA – 10349 – Antenna Placement   Leave a comment


import java.util.*;
import java.io.*;

public class AntennaPlacement {
	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 {
		Scanner in = new Scanner(System.in);
		int tc = in.nextInt();
		while (tc-- > 0) {
			int h = in.nextInt();
			int w = in.nextInt();
			char[][] map = new char[h][];
			for (int i = 0; i < h; i++)
				map[i] = in.next().toCharArray();
			int count = 0;
			for (int i = 0; i < map.length; i++)
				for (int j = 0; j < map[i].length; j++)
					if (map[i][j] == '*')
						count++;
			int[] li = new int[count + 1];
			int[] lj = new int[count + 1];
			int top = 1;
			for (int i = 0; i < map.length; i++)
				for (int j = 0; j < map[i].length; j++)
					if (map[i][j] == '*') {
						li[top] = i;
						lj[top] = j;
						top++;
					}
			int[][] g = new int[count + 2][count + 2];
			for (int i = 1; i <= count; i++) {
				if ((li[i] + lj[i]) % 2 == 0)
					g[0][i] = 1;
				else
					g[i][count + 1] = 1;
			}
			for (int i = 1; i <= count; i++)
				if ((li[i] + lj[i]) % 2 == 0)
					for (int j = 1; j <= count; j++) {
						if ((Math.abs(li[i] - li[j]) == 1 && Math.abs(lj[i]
								- lj[j]) == 0)
								|| (Math.abs(li[i] - li[j]) == 0 && Math
										.abs(lj[i] - lj[j]) == 1)) {
							g[i][j] = 1;
						}
					}
			int matching = maxFlow(0, g.length - 1, g);
			System.out.println(count - matching);
		}
	}
}

Posted February 2, 2012 by epicrado in Bipartite matching

UVA – 11159 – Factors and Multiples   Leave a comment


import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
	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) {
		Scanner in = new Scanner(System.in);
		int tc = in.nextInt();
		int cc = 1;
		while (tc-- > 0) {
			int n = in.nextInt();
			LinkedList<Integer> cache = new LinkedList<Integer>();
			for (int i = 0; i < n; i++)
				cache.add(in.nextInt());
			int m = in.nextInt();
			int[] g = new int[m + n + 2];
			int top = 1;
			for (int i : cache) {
				g[top++] = i;
			}
			for (int i = 0; i < m; i++)
				g[top++] = in.nextInt();
			int[][] res = new int[m + n + 2][m + n + 2];
			for (int i = 1; i <= n; i++)
				res[0][i] = 1;
			for (int i = n + 1; i <= m + n; i++)
				res[i][m + n + 1] = 1;
			for (int i = 1; i <= n; i++)
				for (int j = n + 1; j <= m + n; j++)
					if ((g[i] != 0 && g[j] % g[i] == 0)
							|| (g[i] == 0 && g[j] == 0))
						res[i][j] = 1;
			System.out
					.printf("Case %d: %d\n", cc++, maxFlow(0, m + n + 1, res));
		}
	}
}

Posted February 1, 2012 by epicrado in Bipartite matching, Maxflow