Archive for the ‘Graphs’ Category

UVA – 1062 – Containers   Leave a comment


Minimum path cover on a dag, I believe it can be also solved using a greedy algorithm.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;

public class UVa1062 {
	boolean[] v;
	int[] pair;
	LinkedList<Integer>[] G;

	public int path(int i) {
		if (v[i])
			return 0;
		v[i] = true;
		for (int j : G[i])
			if (pair[j] == -1 || path(pair[j]) != 0) {
				pair[j] = i;
				return 1;
			}
		return 0;
	}

	public int match() {
		int match = 0;
		Arrays.fill(pair, -1);
		for (int i = 0; i < G.length; i++) {
			Arrays.fill(v, false);
			match += path(i);
		}
		return match;
	}

	public void run() throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		v = new boolean[1005];
		pair = new int[1005];
		int cc = 1;
		while (true) {
			char[] arr = in.readLine().trim().toCharArray();
			if (arr.length == 3 && arr[0] == 'e' && arr[1] == 'n'
					&& arr[2] == 'd')
				return;
			G = new LinkedList[arr.length];
			for (int i = 0; i < G.length; i++) {
				G[i] = new LinkedList<Integer>();
				for (int j = i + 1; j < arr.length; j++)
					if (arr[j] <= arr[i])
						G[i].add(j);

			}
			System.out.printf("Case %d: %d\n", cc++, arr.length - match());
		}
	}

	public static void main(String[] args) throws Exception {
		(new UVa1062()).run();
	}
}

Posted November 15, 2012 by epicrado in DAG, Graphs

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());
		}
	}

}

Posted October 27, 2012 by epicrado in Maxflow

Spoj – ANGELS   Leave a comment


maximum matching on a bipartite graph.

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define sz(a)((int)((a).size()))
using namespace std;
vector<int> g[18005];
int gpair[18005];
bool v[18005];
int ver[305][305];
int hor[305][305];
char map[305][305];
int alterpath(int i) {
	if (v[i])
		return 0;
	v[i] = true;
	for (int j = 0; j < sz(g[i]) ; j++)
		if (gpair[g[i][j]] == -1 || alterpath(gpair[g[i][j]])) {
			gpair[g[i][j]] = i;
			return 1;
		}
	return 0;
}
int max_match(int top) {
	for (int i = 0; i < top; i++)
		gpair[i] = -1;
	int match = 0;
	for (int i = 0; i < top; i++) {
		for (int j = 0; j < top; j++)
			v[j] = 0;
		match += alterpath(i);
	}
	return match;
}
int main(int argc, char **argv) {
	int tc;
	scanf("%d", &tc);
	while (tc-- > 0) {
		int w, h;
		scanf("%d %d", &h, &w);
		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++) {
				char c;
				while ((c = getchar()) < 'A')
					;
				map[i][j] = c;
			}
		}
		int top = 0;
		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++) {
				if (map[i][j] != 'A') {
					if (i == 0 || map[i - 1][j] == 'A')
						ver[i][j] = top++;
					else
						ver[i][j] = ver[i - 1][j];
					if (j == 0 || map[i][j - 1] == 'A')
						hor[i][j] = top++;
					else
						hor[i][j] = hor[i][j - 1];
				}
			}
		}
		for (int i = 0; i < top; i++)
			g[i].clear();
		for (int i = 0; i < h; i++)
			for (int j = 0; j < w; j++)
				if (map[i][j] == 'H') {
					g[ver[i][j]].push_back(hor[i][j]);
				}
		printf("%d\n", max_match(top));
	}
	return 0;
}


Posted October 25, 2012 by epicrado in Graphs

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 – 12274 – Jumping monkey   Leave a comment


#include <stdio.h>
int q[1<<22];
int lg2[1<<22];
int g[22];
char v[1<<21];
int next[1<<21];
int parent[1<<21];
int choice[1<<21];
int out[1001];
int h,t;
int isEmpty()
{
	return (t-h+(1<<22))%(1<<22)==0;
}
void enq(int n)
{
	q[t]=n;
	t=(t+1)%(1<<22);
}
void clear()
{
	h = t = 0;
}
int deq()
{
	int res = q[h];
	h = (h+1)%(1<<22);
	return res;
}
int main()
{
	int n,m,i,j,k,l;
	for(i=0;i<22;i++)
		lg2[1<<i]=i;
	while(1)
	{
		scanf("%d %d",&n,&m);
		
		if(!n&&!m)break;
		
		for(i = 0;i<n;i++)g[i]=0;
		
		for(i = 0;i<m;i++)
		{
			scanf("%d %d",&k,&l);
			g[k]|=(1<<l);
			g[l]|=(1<<k);
		}
		
		for(i = 0;i<1<<n;i++)
			next[i]=v[i]=0;
		
		for(i = 1;i<1<<n;i++)
			next[i]=next[i-(i&-i)]|g[lg2[i&-i]];
		
		clear();
		
		enq((1<<n)-1);
		v[(1<<n)-1]=1;
		int f = 0;
		while(!isEmpty())
		{
			int current = deq();
			if(!current)
			{
				int top = 0;
				while(current!=(1<<n)-1)
				{
					out[top++]=choice[current];
					current = parent[current];
				}
				printf("%d:",top);
				--top;
				while(top>=0)
					printf(" %d",out[top--]);
				putchar('\n');
				f = 1;
				break;
			}
			int mask = current;
			while(mask!=0)
			{
				int nx = next[current^(mask&-mask)];
				if(!v[nx])
				{
					v[nx]=1;
					enq(nx);
					parent[nx]=current;
					choice[nx]=lg2[(mask&-mask)];
				}
				mask-=mask&-mask;
			}
		}
		if(!f)
			puts("Impossible");
	}
	return 0;
}

Posted July 29, 2012 by epicrado in Breadth first search, Dynamic programming

UVA – 1189 – Find The Multiple   1 comment


Can be solved also using BFS reducing the number of states to MOD only :).

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

public class Multiples {
	static int MOD;
	static int[][] dp;
	static int[][] choice;

	public static int go(int i, int mod) {
		if (mod == 0)
			return i;
		else if (i > 100)
			return 1 << 25;
		else if (dp[i][mod] != -1)
			return dp[i][mod];
		int a = go(i + 1, (mod * 10 + 1) % MOD);
		int b = go(i + 1, (mod * 10 + 0) % MOD);
		if (a <= b)
			choice[i][mod] = 1;
		else
			choice[i][mod] = 0;
		return dp[i][mod] = (a < b) ? a : b;
	}

	public static void main(String[] args) throws Exception {
		InputReader in = new InputReader(System.in);
		while (true) {
			MOD = in.nextInt();
			if (MOD == 0)
				break;
			dp = new int[101][MOD];
			choice = new int[101][MOD];
			for (int i = 0; i < dp.length; i++)
				Arrays.fill(dp[i], -1);
			go(1, 1 % MOD);
			String res = "1";
			int i = 1;
			int m = 1 % MOD;
			while (m != 0) {
				res = res + choice[i][m];
				m = (m * 10 + choice[i][m]) % MOD;
				i++;
			}
			System.out.println(res);
		}
	}

	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 July 20, 2012 by epicrado in Dynamic programming, Graphs, Mathematics

UVA – 10926 – How Many Dependencies?   Leave a comment


Use floyd warshall to do transitive closure and then choose the best node.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class HowManyDependancies {

	public static void main(String[] args) throws Exception {
		InputReader in = new InputReader(System.in);
		while (true) {
			int n = in.nextInt();
			if (n == 0)
				return;
			int[][] g = new int[n][n];
			for (int i = 0; i < n; i++) {
				int d = in.nextInt();
				for (int j = 0; j < d; j++)
					g[i][in.nextInt() - 1] = 1;
			}
			for (int k = 0; k < n; k++)
				for (int i = 0; i < n; i++)
					for (int j = 0; j < n; j++)
						g[i][j] |= g[i][k] & g[k][j];
			int max = 0;
			int maxCount = 0;
			for (int i = 0; i < g.length; i++)
				maxCount += g[0][i];
			for (int i = 1; i < g.length; i++) {
				int cc = 0;
				for (int j = 0; j < n; j++)
					cc += g[i][j];
				if (cc > maxCount) {
					max = i;
					maxCount = cc;
				}
			}
			System.out.println(max+1);
		}
	}

	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 July 5, 2012 by epicrado in Floyd warshall