Archive for the ‘Minimum spanning tree’ Category

UVA – 10397 – Connect the Campus   Leave a comment


same as 10147 except that here output is the distance not the edges
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
typedef struct edge
{
	int f,t;
	double d;
}E;
int getParent(int i,int *set)
{
	if(i==set[i])
		return i;
	else
		return (set[i]=getParent(set[i],set));
}
int isUnion(int a,int b,int* set)
{
	return getParent(a,set)==getParent(b,set);
}
void makeUnion(int a,int b,int* set)
{
	set[getParent(a,set)] = getParent(b,set);
}
double distance(int x1,int y1,int x2,int y2)
{
	return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
int cmp(const void* a,const void* b)
{
	if((*(E*)a).d<(*(E*)b).d)
		return -1;
	else
		return 1;
}
int main()
{
	int nodes[1000][2];
	E edgeList[300000];
	int set[1000],i,j,n,e,f,s,t,done;
	double res;
	while(scanf("%d",&n)==1)
	{
		e = 0;
		for(i=1;i<=n;i++)
			scanf("%d %d",nodes[i],nodes[i]+1);

		for(i=1;i<=n;i++)
			for(j=i+1;j<=n;j++)
			{
				edgeList[e].f=i;
				edgeList[e].t=j;
				edgeList[e].d=distance(nodes[i][0],nodes[i][1],nodes[j][0],nodes[j][1]);
				e++;
			}
		done = 0;
		for(i=1;i<=n;i++)set[i]=i;
		scanf("%d",&f);
		while(f--)
		{
			scanf("%d %d",&s,&t);
			if(!isUnion(s,t,set))
			{
				done++;
				makeUnion(s,t,set);
			}
		}
		qsort(edgeList,e,sizeof(E),&cmp);
		res = 0;
		for(i=0;i<e&&done<n-1;i++)
		{
			if(!isUnion(edgeList[i].f,edgeList[i].t,set))
			{
				res+=edgeList[i].d;
				makeUnion(edgeList[i].f,edgeList[i].t,set);
				done++;
			}
		}
		printf("%.2lf\n",res);
	}
	return  0;
}

Posted August 18, 2011 by epicrado in Minimum spanning tree

UVA – 10842 – Traffic Flow   Leave a comment


MST with minimax
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#define init(i,a,n) for(i=0;i<n;i++)a[i]=i
typedef struct edge
{
	int f,t,d;
}E;
int getParent(int i,int *set)
{
	if(i==set[i])
		return i;
	else
		return (set[i]=getParent(set[i],set));
}
int isUnion(int a,int b,int* set)
{
	return getParent(a,set)==getParent(b,set);
}
void makeUnion(int a,int b,int* set)
{
	set[getParent(a,set)] = getParent(b,set);
}
int cmp(const void*a,const void*b)
{
	return -((E*)a)->d+((E*)b)->d;
}
int main()
{
	int v,c,cc,e,set[200005],i,d,res;
	E list[200005];
	cc=1;
	scanf("%d",&c);
	while(c--)
	{
		res = 100000;
		scanf("%d %d",&v,&e);
		init(i,set,v);
		for(i=0;i<e;i++)
			scanf("%d %d %d",&list[i].f,&list[i].t,&list[i].d);
		qsort(list,e,sizeof(E),&cmp);
		d = 0;
		for(i=0;i<e&&d<v-1;i++)
			if(!isUnion(list[i].f,list[i].t,set))
			{
				makeUnion(list[i].f,list[i].t,set);
				if(list[i].d<res)
					res = list[i].d;
				d++;
			}
		printf("Case #%d: %d\n",cc++,res);
	}
	return 0;
}

Posted August 18, 2011 by epicrado in Minimum spanning tree

UVA – 10462 – Is There A Second Way Left ?   Leave a comment


2nd MST same as 10600
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#define init(i,a,n) for(i=0;i<=n;i++)a[i]=i
#define inf 1000000
typedef struct edge
{
	int f,t,d;
}E;
int getParent(int i,int *set)
{
	if(i==set[i])
		return i;
	else
		return (set[i]=getParent(set[i],set));
}
int isUnion(int a,int b,int* set)
{
	return getParent(a,set)==getParent(b,set);
}
void makeUnion(int a,int b,int* set)
{
	set[getParent(a,set)] = getParent(b,set);
}
int cmp(const void*a,const void*b)
{
	return ((E*)a)->d-((E*)b)->d;
}
int main()
{
	int t,n,e,i,cc,set[105],d,mst,mst2,cmst,j;
	cc=1;
	E list[10005];
	char mark[10005];
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d %d",&n,&e);
		for(i=0;i<e;i++)
			scanf("%d %d %d",&list[i].f,&list[i].t,&list[i].d);
		qsort(list,e,sizeof(E),&cmp);
		init(i,set,n);
		d = 0;
		mst = 0;
		for(i=0;i<e;i++)
			mark[i]=0;
		for(i=0;i<e&&d<n-1;i++)
		{
			if(!isUnion(list[i].f,list[i].t,set))
			{
				d++;
				makeUnion(list[i].f,list[i].t,set);
				mst+=list[i].d;
				mark[i]=1;
			}
		}
		if(d<n-1)
			printf("Case #%d : No way\n",cc++);
		else
		{
			mst2 = inf;
			for(i=0;i<e;i++)
			{
				if(mark[i])
				{

					init(j,set,n);
					cmst = 0;
					for(j=0;j<e;j++)
					{
						if(mark[j]&&j!=i)
						{
							makeUnion(list[j].f,list[j].t,set);
							cmst+=list[j].d;
						}
					}
					d = 0;
					for(j=0;j<e&&!d;j++)
					{
						if(!mark[j]&&!isUnion(list[j].f,list[j].t,set))
						{
							cmst+=list[j].d;
							d=1;
						}
					}
					if(d&&cmst<mst2)
						mst2 = cmst;
				}
			}
			if(mst2!=inf)
				printf("Case #%d : %d\n",cc++,mst2);
			else
				printf("Case #%d : No second way\n",cc++);
		}
	}
	return 0;
}

Posted August 18, 2011 by epicrado in Minimum spanning tree

UVA – 10369 – Arctic Network   Leave a comment


#include <stdio.h>
#include <math.h>
#include <stdlib.h>
typedef struct edge
{
	int f,t;
	double d;
}E;
int getParent(int i,int *set)
{
	if(i==set[i])
		return i;
	else
		return (set[i]=getParent(set[i],set));
}
int isUnion(int a,int b,int* set)
{
	return getParent(a,set)==getParent(b,set);
}
void makeUnion(int a,int b,int* set)
{
	set[getParent(a,set)] = getParent(b,set);
}
double distance(int x1,int y1,int x2,int y2)
{
	return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
int cmp(const void* a,const void* b)
{
	if((*(E*)a).d<(*(E*)b).d)
		return -1;
	else
		return 1;
}
int main()
{
	int nodes[600][2];
	E edgeList[179700];
	int set[600],c,i,j,n,e,S,done;
	double res;
	scanf("%d",&c);
	while(c-->0)
	{
		e = 0;
		scanf("%d %d",&S,&n);
		for(i=0;i<n;i++)
			scanf("%d %d",nodes[i],nodes[i]+1);
		for(i=0;i<n;i++)
			for(j=i+1;j<n;j++)
			{
				edgeList[e].f=i;
				edgeList[e].t=j;
				edgeList[e].d=distance(nodes[i][0],nodes[i][1],nodes[j][0],nodes[j][1]);
				e++;
			}
		done = 0;
		for(i=0;i<n;i++)set[i]=i;
		qsort(edgeList,e,sizeof(E),&cmp);
		res = 0;
		for(i=0;i<e&&done<n-S;i++)
		{
			if(!isUnion(edgeList[i].f,edgeList[i].t,set))
			{
				makeUnion(edgeList[i].f,edgeList[i].t,set);
				if(edgeList[i].d>res)
					res = edgeList[i].d;
				done++;
			}
		}
		printf("%.2lf\n",res);
	}
	return  0;
}

Posted August 18, 2011 by epicrado in Minimum spanning tree

UVA – 10147 – Highways   1 comment


#include <stdio.h>
#include <math.h>
#include <stdlib.h>
typedef struct edge
{
	int f,t;
	double d;
}E;
int getParent(int i,int *set)
{
	if(i==set[i])
		return i;
	else
		return (set[i]=getParent(set[i],set));
}
int isUnion(int a,int b,int* set)
{
	return getParent(a,set)==getParent(b,set);
}
void makeUnion(int a,int b,int* set)
{
	set[getParent(a,set)] = getParent(b,set);
}
double distance(int x1,int y1,int x2,int y2)
{
	return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
int cmp(const void* a,const void* b)
{
	if((*(E*)a).d<(*(E*)b).d)
		return -1;
	else
		return 1;
}
int main()
{
	int nodes[1000][2];
	E edgeList[300000];
	int set[1000],c,i,j,n,e,f,s,t,done;
	scanf("%d",&c);
	while(c-->0)
	{
		e = 0;
		scanf("%d",&n);
		for(i=1;i<=n;i++)
			scanf("%d %d",nodes[i],nodes[i]+1);
		for(i=1;i<=n;i++)
			for(j=i+1;j<=n;j++)
			{
				edgeList[e].f=i;
				edgeList[e].t=j;
				edgeList[e].d=distance(nodes[i][0],nodes[i][1],nodes[j][0],nodes[j][1]);
				e++;
			}
		done = 0;
		scanf("%d",&f);
		for(i=1;i<=n;i++)set[i]=i;
		while(f-->0)
		{
			scanf("%d %d",&s,&t);
			if(!isUnion(s,t,set))
			{
				done++;
				makeUnion(s,t,set);
			}
		}
		qsort(edgeList,e,sizeof(E),&cmp);
		if(done==n-1)
			puts("No new highways need");
		for(i=0;i<e&&done<n-1;i++)
		{
			if(!isUnion(edgeList[i].f,edgeList[i].t,set))
			{
				printf("%d %d\n",edgeList[i].f,edgeList[i].t);
				makeUnion(edgeList[i].f,edgeList[i].t,set);
				done++;
			}
		}
		if(c)
			putchar('\n');
	}
	return  0;
}

Posted August 18, 2011 by epicrado in Minimum spanning tree

UVA – 11733 – Airports   Leave a comment


MST + Counting connected components using disjointSet
#include <stdio.h>
#include <stdlib.h>
#define init(i,a,n) for(i=1;i<=n;i++)a[i]=i
typedef struct Edge{int f,t,w;}E;
E roads[100005];
int set[10005];
int getParent(int i,int *set)
{
	if(i==set[i])
		return i;
	else
		return (set[i]=getParent(set[i],set));
}
int isUnion(int a,int b,int* set)
{
	return getParent(a,set)==getParent(b,set);
}
void makeUnion(int a,int b,int* set)
{
	set[getParent(a,set)] = getParent(b,set);
}
int cmp(const void*a,const void*b)
{
	return ((E*)a)->w-((E*)b)->w;
}
int main()
{
	int c,cc,n,v,i,j,cost,total,air;
	scanf("%d",&c);
	cc=1;
	while(c--)
	{
		scanf("%d %d %d",&n,&v,&cost);
		for(i=0;i<v;i++)
			scanf("%d %d %d",&roads[i].f,&roads[i].t,&roads[i].w);
		qsort(roads,v,sizeof(E),&cmp);
		init(i,set,n);
		total = 0;
		j=0;
		air = 0;
		for(i=0;i<v&&j<n-1&&roads[i].w<cost;i++)
		{
			if(!isUnion(roads[i].t,roads[i].f,set))
			{
					total+=roads[i].w;
					makeUnion(roads[i].t,roads[i].f,set);
					j++;
			}
		}
		for(i=1;i<=n;i++)
		{
			total+=cost*(set[i]==i);
			air+=(set[i]==i);
		}
		printf("Case #%d: %d %d\n",cc++,total,air);
	}
	return 0;
}

Posted August 17, 2011 by epicrado in Minimum spanning tree

UVA – 11267 – The Hire-a-Coder Business Model   Leave a comment


Solution is in the last two functions other than that that's little data structures implementations
this problem is testing for bipartite graph and MST however there's a little modification in MST
we want to minimize the loss as much as possible so after we do the MST algorithm and take
those edges to keep the graph connected there may be extra negative edges we should take those with us aswell
cause it represents a gain to us ( loss for the company as becomes minimum as possible )
#include <stdio.h>
#include <stdlib.h>
#define init(i,a,n) for(i=1;i<=n;i++)a[i]=i
#define inf 10000000
typedef struct edge
{
	int f,t,d;
}E;
char matrix[205][205];
int mark[205];
int set[205];
E list[40000];
typedef struct dNode
{
	int content;
	struct dNode* next;
	struct dNode* prev;
}node;
typedef struct dLinkedList
{
	node header;
	node trailer;
	int size;
}linkedList;
linkedList* LinkedList()
{
	linkedList* l = (linkedList*) malloc(sizeof(linkedList));
	(l->header).next = &(l->trailer);
	(l->trailer).prev = &(l->header);
	l->size = 0;
	return l;
}
int getParent(int i,int *set)
{
	if(i==set[i])
		return i;
	else
		return (set[i]=getParent(set[i],set));
}
int isUnion(int a,int b,int* set)
{
	return getParent(a,set)==getParent(b,set);
}
void makeUnion(int a,int b,int* set)
{
	set[getParent(a,set)] = getParent(b,set);
}
void push_back(int val,linkedList* l)
{
	node* n = (node*) malloc(sizeof(node));
	n->content = val;
	n->next = &(l->trailer);
	n->prev = l->trailer.prev;
	(l->trailer.prev)->next = n;
	l->trailer.prev = n;
	l->size++;
}
int pop_front(linkedList*l)
{
	int  res;
	node* n = l->header.next;
	l->header.next = n->next;
	n->next->prev = &(l->header);
	res = n->content;
	free(n);
	l->size--;
	return res;
}
int cmp(const void*a,const void*b)
{
	return ((E*)a)->d-((E*)b)->d;
}
int validate(int n)
{
	int i,j,c,ex;
	for(i=1;i<=n;i++)
		mark[i] = 0;
	linkedList* Q = LinkedList();
	for(j=1;j<=n;j++)
		if(!mark[j])
		{
			mark[j]=1;
			push_back(j,Q);
			while(Q->size)
			{
				c = pop_front(Q);
				ex = mark[c]^3;
				for(i=1;i<=n;i++)
					if(matrix[c][i])
					{
						if(!mark[i])
						{
							mark[i] = ex;
							push_back(i,Q);
						}
						if(mark[i]!=ex)
							return 0;
					}
			}
		}
	return 1;
}
int main()
{
	register int i,j,res,d;
	int n,e;
	scanf("%d",&n);
	while(n)
	{
		scanf("%d",&e);
		for(i=1;i<=n;i++)
			for(j=1;j<=n;j++)
				matrix[i][j]=0;
		for(i=0;i<e;i++)
		{
			scanf("%d %d %d",&list[i].f,&list[i].t,&list[i].d);
			matrix[list[i].f][list[i].t]=matrix[list[i].t][list[i].f]=1;
		}
		if(!validate(n))
			puts("Invalid data, Idiot!");
		else
		{
			init(i,set,n);
			res = 0;
			d = 0;
			qsort(list,e,sizeof(E),&cmp);
			for(i=0;i<e&&d<n-1;i++)
				if(!isUnion(list[i].f,list[i].t,set))
				{
					makeUnion(list[i].f,list[i].t,set);
					res+=list[i].d;
					d++;
				}
				else if(list[i].d<0)
					res+=list[i].d;
			for(;i<e&&list[i].d<0;i++)
				res+=list[i].d;
			printf("%d\n",res);
		}
		scanf("%d",&n);
	}
	return 0;
}

Posted August 16, 2011 by epicrado in Breadth first search, Minimum spanning tree