## 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

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

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

### Re: 10842 - Traffic Flow

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

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....