Archive for the ‘Floyd warshall’ Category

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

UVA – 1243 – Polynomial-time Reductions   Leave a comment


First we compress the SCC and count the relations needed by each SCC add them to total, then using the graph’s transitive closure we eliminate the extra edges however we need to eliminate them in topological order of nodes.

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

public class PolynomialTimeReduction {
	public static int find(int i, int[] p) {
		return p[i] = (p[i] == i) ? i : find(p[i], p);
	}

	public static void topsort(int i, boolean[] v, byte[][] g,
			Stack<Integer> sort) {
		if (!v[i]) {
			v[i] = true;
			for (int j = 0; j < g.length; j++)
				if (g[i][j] != 0)
					topsort(j, v, g, sort);
			sort.push(i);
		}
	}

	public static void main(String[] args) throws Exception {
		InputReader in = new InputReader(System.in);
		int cc = 1;
		while (true) {
			int n = in.nextInt();
			int m = in.nextInt();
			if (n == 0 && m == 0)
				return;
			byte[][] g = new byte[n][n];
			for (int i = 0; i < m; i++)
				g[in.nextInt() - 1][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[] p = new int[n];
			for (int i = 0; i < n; i++)
				p[i] = i;
			int c = n;
			for (int i = 0; i < g.length; i++)
				for (int j = 0; j < g.length; j++)
					if (g[i][j] == 1 && g[j][i] == 1
							&& find(i, p) != find(j, p)) {
						p[find(i, p)] = find(j, p);
						c--;
					}
			int[] count = new int[n];
			byte[][] g2 = new byte[c][c];
			int top = 0;
			int tot = 0;
			for (int i = 0; i < n; i++)
				count[p[i]]++;
			for (int i = 0; i < n; i++)
				if (count[i] > 1)
					tot += count[i];
			for (int i = 0; i < count.length; i++) {
				if (count[i] != 0)
					count[i] = top++;// map back
			}
			for (int i = 0; i < g.length; i++) {
				for (int j = 0; j < g.length; j++) {
					g2[count[p[i]]][count[p[j]]] = g[i][j];
				}
			}
			for (int i = 0; i < g2.length; i++)
				g2[i][i] = 0;
			boolean[] v = new boolean[c];
			Stack<Integer> toposort = new Stack<Integer>();
			for (int i = 0; i < c; i++)
				topsort(i, v, g2, toposort);
			while (!toposort.isEmpty()) {
				int current = toposort.pop();
				for (int j = 0; j < c; j++) {
					if (g2[current][j] == 1) {
						for (int k = 0; k < c; k++) {
							g2[current][k] ^= g2[j][k] & g2[current][k];
						}
					}
				}
				for (int i = 0; i < g2.length; i++)
					tot += g2[current][i];
			}
			System.out.printf("Case %d: %d\n", cc++, tot);
		}
	}

	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 24, 2012 by epicrado in Floyd warshall, Topological sort

UVA – 334 – Identifying Concurrent Events   Leave a comment


Two events are concurrent if there’s no path between them in either direction, So we use floyd warshall to get the transitive closure of the graph (T) and find i,j where (T[i][j] == 0 AND T[j][i] == 0).

#include <stdio.h>
#include <iostream>
#include <vector>
#include <map>
#include <string>
using namespace std;
int main() {
	int cc = 1;
	while (1) {
		int n;
		cin >> n;
		if (n == 0)
			break;
		vector<string> mapbk;
		map<string, int> map;
		char g[200][200];
		for (int i = 0; i < 200; i++)
			for (int j = 0; j < 200; j++)
				g[i][j] = 0;
		int top = 0;
		for (int i = 0; i < n; i++) {
			int m;
			cin >> m;
			int first = top;
			for (int j = 0; j < m; j++) {
				string s;
				cin >> s;
				map[s] = top;
				mapbk.push_back(s);
				top++;
			}
			for (int j = first; j < top - 1; j++)
				g[j][j + 1] = 1;
		}
		int m;
		cin >> m;
		for (int i = 0; i < m; i++) {
			string s1, s2;
			cin >> s1 >> s2;
			g[map[s1]][map[s2]] = 1;
		}
		for (int k = 0; k < top; k++)
			for (int i = 0; i < top; i++)
				for (int j = 0; j < top; j++)
					g[i][j] |= g[i][k] & g[k][j];
		string out = "";
		int count = 0;
		for (int i = 0; i < top; i++)
			for (int j = i + 1; j < top; j++) {
				if (!g[i][j] && !g[j][i]) {
					count++;
					if (count <= 2)
						out = out + "(" + mapbk[i] + "," + mapbk[j] + ") ";
				}
			}
		if (count != 0) {
			cout << "Case " << cc++ << ", " << count << " concurrent events:"
					<< endl;
			cout << out << endl;
		} else {
			cout << "Case " << cc++ << ", no concurrent events." << endl;
		}
	}
	return 0;
}

Posted June 16, 2012 by epicrado in Floyd warshall

UVA – 10816 – Travel in Desert   1 comment


The problem here is asking us to find the shortest path between two nodes in a graph, under constraint that the maximum temperature of any edge used in this path is minimum.
I’ll explain two ways to solve this problem

One way would be using floyd warshall’s first to determine the minimum temperature of the path, then we build a graph using only the edges that have temperature <= minimum temperature if there's more than one edge having this property between two nodes its obvious that we should use the one with minimum weight (since we'll be looking for the shortest path), then we use floyd warshall's again or any other shortest path algorithm to find the distance between the start and destination in this new graph, see implementation for more details.

Another way would be to binary search on the minimum temperature and use any shortest path algorithm to find the shortest path between start and destination bellman ford should be a good choice as its easy to implement and will handle the problem of the multiple edges between two nodes automatically.
Both methods have almost the same running time O(V^3) vs. O(VE log 300)

You may notice that in the second way we don’t really have to run bellman ford inside the binary search instead we may run a simple O(V+E) dfs to check that destination is reachable from start that would make the running time O(VE).

#include <stdio.h>
#define inf 1e9
int a, b;
int s[10005], t[10005];
float dp[105][105];
int path[105][105];
float r[10005], d[10005];
float max(float a,float b){return (a>b)?a:b;}
float min(float a,float b){return (a<b)?a:b;}
float absval(float a){return (a<0)?-a:a;}
void printPath(int i, int j, char p) {
	if (!path[i][j]) {
		if (!p)
			printf("%d ", i);
		printf("%d", j);
		if (j != b)//if j is not the final node
			putchar(' ');
	} else {
		printPath(i, path[i][j], p);
		printPath(path[i][j], j, 1);
	}
}
int main() {
	int n, e, i, j, k;
	while (scanf("%d %d", &n, &e) == 2) {
		scanf("%d %d", &a, &b);
		for (i = 1; i <= n; i++)
			for (j = 1; j <= n; j++)
				dp[i][j] = inf;
		for (i = 0; i < e; i++) {
			scanf("%d %d %f %f", s + i, t + i, r + i, d + i);
			dp[s[i]][t[i]] = min(dp[s[i]][t[i]],r[i]);
			dp[t[i]][s[i]] = min(dp[t[i]][s[i]],r[i]);
		}
		//use floyd warshall to find the lowest tempreture
		for (k = 1; k <= n; k++)
			for (i = 1; i <= n; i++)
				for (j = 1; j <= n; j++)
					dp[i][j] = min(dp[i][j],max(dp[i][k],dp[k][j]));
		float minTemp = dp[a][b];
		//refill floyd warshall array with edge weights
		//given each edge has minimum weight and tempreture less than lowest tempreture
		for (i = 1; i <= n; i++)
			for (j = 1; j <= n; j++) {
				dp[i][j] = inf;
				path[i][j] = 0;
			}
		for (i = 0; i < e; i++) {
			if (r[i]<minTemp+1e-6) {
				//if there are multiple edges between two nodes,greedily choose the one with smaller length
				dp[s[i]][t[i]] = min(dp[s[i]][t[i]],d[i]);
				dp[t[i]][s[i]] = min(dp[t[i]][s[i]],d[i]);
			}
		}
		//floyd warshall again but this time we'll store the intermidate node for each two nodes to allow path retrival
		for (k = 1; k <= n; k++)
			for (i = 1; i <= n; i++)
				for (j = 1; j <= n; j++)
					if (dp[i][j] > dp[i][k] + dp[k][j]) {
						dp[i][j] = dp[i][k] + dp[k][j];
						path[i][j] = k;
					}
		printPath(a, b, 0);
		putchar('\n');
		printf("%.1f %.1f\n", dp[a][b], minTemp);
	}
	return 0;
}

Posted June 12, 2012 by epicrado in Bellman Ford's, Floyd warshall, Graphs

1056 – Degrees of Separation   Leave a comment


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

public class DegreesOfSep {
	public static void main(String[] args) throws Exception {
		InputReader in = new InputReader(System.in);
		int cc = 1;
		while (true) {
			int n = in.nextInt();
			int e = in.nextInt();
			if (n == 0 && e == 0)
				break;
			int[][] dp = new int[n][n];
			int top = 0;
			for (int[] i : dp)
				Arrays.fill(i, 127);
			for (int i = 0; i < dp.length; i++)
				dp[i][i] = 0;
			TreeMap<String, Integer> map = new TreeMap<String, Integer>();
			for (int i = 0; i < e; i++) {
				String s1 = in.next();
				String s2 = in.next();
				if (!map.containsKey(s1))
					map.put(s1, top++);
				if (!map.containsKey(s2))
					map.put(s2, top++);
				int a = map.get(s1);
				int b = map.get(s2);
				dp[a][b] = dp[b][a] = 1;
			}
			for (int k = 0; k < dp.length; k++)
				for (int i = 0; i < dp.length; i++)
					for (int j = 0; j < dp.length; j++)
						dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k][j]);
			int max = 0;
			for (int i = 0; i < dp.length; i++)
				for (int j = 0; j < dp.length; j++)
					max = Math.max(max, dp[i][j]);
			if (max != 127)
				System.out.printf("Network %d: %d\n\n", cc++, max);
			else
				System.out.printf("Network %d: DISCONNECTED\n\n", cc++, max);

		}
	}

	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 April 19, 2012 by epicrado in Floyd warshall, Graphs

UVA – 1198 – The Geodetic Set Problem   Leave a comment


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

public class GeodeticSetProblem {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = Integer.parseInt(in.nextLine());
		long[][] path = new long[n + 1][n + 1];
		int[][] shortest = new int[n + 1][n + 1];
		for (int i = 0; i < shortest.length; i++) {
			Arrays.fill(shortest[i], 63);
			shortest[i][i] = 0;
		}
		for (int i = 1; i <= n; i++)
			path[i][i] = 1L << i;
		for (int i = 1; i <= n; i++) {
			String[] inp = in.nextLine().split(" ");
			for (int j = 0; j < inp.length; j++) {
				int k = Integer.parseInt(inp[j]);
				shortest[i][k] = 1;
				path[i][k] = path[i][i] | path[k][k];
			}
		}
		for (int k = 1; k <= n; k++)
			for (int i = 1; i <= n; i++)
				for (int j = 1; j <= n; j++) {
					if (shortest[i][j] == shortest[i][k] + shortest[k][j]) {
						path[i][j] |= path[i][k] | path[j][k];
					} else if (shortest[i][j] > shortest[i][k] + shortest[k][j]) {
						shortest[i][j] = shortest[i][k] + shortest[k][j];
						path[i][j] = path[i][k] | path[j][k];
					}
				}
		int tc = Integer.parseInt(in.nextLine());
		while (tc-- > 0) {
			String[] inp = in.nextLine().split(" ");
			int[] ind = new int[inp.length];
			for (int i = 0; i < inp.length; i++)
				ind[i] = Integer.parseInt(inp[i]);
			long res = 0;
			for (int i = 0; i < inp.length; i++)
				for (int j = i; j < inp.length; j++) {
					res |= path[ind[i]][ind[j]];
				}
			if (res == ((1L << n) - 1) << 1)
				System.out.println("yes");
			else
				System.out.println("no");

		}
	}
}

Posted January 27, 2012 by epicrado in Floyd warshall

UVA – 567 – Risk   Leave a comment


Can be solved using bfs but I've used floyd warshall here cause multiple queries are asked
#include <stdio.h>
#define inf 10000
int min(int a,int b)
{
	return (a<b)?a:b;
}
int main()
{
	int map[21][21],i,j,k,n,cc,lineCount,dest;
	cc = 1;
	while(scanf("%d",&n)==1)
	{
		for(i=0;i<21;i++)
		{
			for(j=0;j<21;j++)
				map[i][j]=inf;
			map[i][i]=0;
		}
		lineCount = 1;
		for(i=0;i<n;i++)
		{
			scanf("%d",&dest);
			map[lineCount][dest] = map[dest][lineCount] = 1;
		}
		lineCount++;
		while(lineCount<20)
		{
			scanf("%d",&n);
			for(i=0;i<n;i++)
			{
				scanf("%d",&dest);
				map[lineCount][dest] = map[dest][lineCount] = 1;
			}
			lineCount++;
		}
		for(k=1;k<21;k++)
			for(i=1;i<21;i++)
				for(j=1;j<21;j++)
					map[i][j]=min(map[i][j],map[i][k]+map[k][j]);
		scanf("%d",&n);
		printf("Test Set #%d\n",cc++);
		while(n--)
		{
			scanf("%d %d",&i,&j);
			printf("%2d to %2d: %d\n",i,j,map[i][j]);
		}
		putchar('\n');
	}
	return 0;
}

Posted August 23, 2011 by epicrado in Breadth first search, Floyd warshall