10842 - Traffic Flow

All about problems in Volume 108. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Chirag Chheda
Learning poster
Posts: 74
Joined: Sat Jun 21, 2008 12:24 pm
Location: India

Re: 10842 - Traffic Flow

Post by Chirag Chheda » Sat Feb 28, 2009 6:33 am

Any ways i figured it out. It says to calculate the maximum spanning tree and find out its minimum weight road. :D

asif_khan_ak_07
New poster
Posts: 25
Joined: Fri Apr 17, 2009 8:24 am

Re: 10842 - Traffic Flow

Post by asif_khan_ak_07 » Sat Dec 19, 2009 6:03 pm

i am getting WA..any special I/0

Code: Select all

#include<stdio.h>
#define MAX 105
#define INFINITY 10000000
int cost[MAX][MAX];
int len[MAX];
bool intree[MAX];
int n,m;
void ini(){
	for(int i=0;i<n;i++){
		intree[i]=false;
		len[i]=0;
	}
}
void update(int v){
	for(int i=0;i<n;i++){
		if(cost[v][i]!=0 && len[i]<cost[v][i])
			len[i]=cost[v][i];
	}
}
int prims(){
	int last,mn;
	intree[0]=true;
	update(0);
	last=INFINITY;
	for(int i=1;i<n;i++){
		mn=-1;
		for(int j=0;j<n;j++){
			if(!intree[j]){
				if(mn==-1 || len[mn]<len[j]){
					mn=j;
					
				}

			}
		}
		
	//	printf("%d ",len[mn]);
		if(len[mn]<last) last=len[mn]; intree[mn]=true; update(mn);
	}
	return last;

}
void in(){
	for(int i=0;i<n;i++) for(int j=0;j<n;j++) cost[i][j]=0; 
}
int main(){
	int tc;
	freopen("a.txt","r",stdin);
	int u,v,c,ans;
	scanf("%d",&tc);
	for(int z=0;z<tc;z++){
		scanf("%d %d",&n,&m);
		in();
		for(int i=0;i<m;i++){
			scanf("%d %d %d",&u,&v,&c);
			cost[u][v]=cost[v][u]=c;
		}
		ini();
		ans=prims();
		if(ans==INFINITY) ans=len[0];
		printf("Case #%d: %d\n",z+1,ans);
	}
	return 0;
}

Imti
Learning poster
Posts: 53
Joined: Sat Dec 04, 2010 12:00 pm
Location: Bangladesh
Contact:

Re: 10842 - Traffic Flow

Post by Imti » Sat Jun 11, 2011 7:06 pm

There is no input like:

Code: Select all

1
1 3
0 0 950
0 0 800
0 0 900
My acc code don't care about this.... :)

Post Reply

Return to “Volume 108 (10800-10899)”