Archive for the ‘DAG’ 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 – 10285 – Longest Run on a Snowboard   Leave a comment


#include <stdio.h>
int map[105][105];
int dp[105][105];
int n,m;
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
int max(int a,int b)
{
	return (a>b)?a:b;
}
int longestRun(int i,int j)
{
	if(dp[i][j]!=-1)
		return dp[i][j];
	else
	{
		int res = 0;
		int d,x,y;
		for(d=0;d<4;d++)
		{
			y = i + dy[d];
			x = j + dx[d];
			if(x>=0&&y>=0&&y<n&&x<m&&map[y][x]<map[i][j])
				res = max(res,1+longestRun(y,x));
		}
		return dp[i][j]=res;
	}
}
int main()
{
	int N,r,c,i,j,mx;
	char area[20];
	scanf("%d",&N);
	while(N--)
	{
		scanf("%s %d %d",area,&r,&c);
		n = r;
		m = c;
		for(i=0;i<r;i++)
			for(j=0;j<c;j++)
			{
				scanf("%d",&map[i][j]);
				dp[i][j]=-1;
			}
		mx = 0;
		for(i=0;i<r;i++)
			for(j=0;j<c;j++)
				mx = max(mx,longestRun(i,j));
		printf("%s: %d\n",area,mx+1);
	}
	return 0;
}

Posted August 19, 2011 by epicrado in DAG

UVA – 10000 – Longest Paths   2 comments


solved using dfs + memo
#include <stdio.h>
char map[200][200];
int dp[200][200];
int max(int a,int b)
{
	return(a>b)?a:b;
}
int length(int s,int t,int n)
{
	if(dp[s][t]!=-1)
		return dp[s][t];
	else
	{
		int maximum = -1;
		int i;
		for(i=1;i<=n;i++)
			if(map[s][i])
				maximum = max(maximum,1+length(i,t,n));
		return dp[s][t]=maximum;
	}
}
int main()
{
	int n,a,b,i,s,j,best,m,c;
	c = 1;
	scanf("%d",&n);
	while(n)
	{
		scanf("%d",&s);
		for(i=0;i<=n;i++)
		{
			for(j=0;j<=n;j++)
			{
				map[i][j]=0;
				dp[i][j]=-1;
			}
			dp[i][i]=0;
		}
		scanf("%d %d",&a,&b);
		while(a||b)
		{
			map[a][b]=1;
			scanf("%d %d",&a,&b);
		}
		m = -1;
		best = 0;
		for(i=1;i<=n;i++)
			if(length(s,i,n)>m)
			{
				m = length(s,i,n);
				best = i;
			}
		printf("Case %d: The longest path from %d has length %d, finishing at %d.\n\n",c++,s,m,best);
		scanf("%d",&n);
	}
	return 0;
}

Posted August 17, 2011 by epicrado in DAG