![:D](./images/smilies/icon_biggrin.gif)
10842 - Traffic Flow
Moderator: Board moderators
-
- 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. ![:D](./images/smilies/icon_biggrin.gif)
![:D](./images/smilies/icon_biggrin.gif)
-
- 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;
}
Re: 10842 - Traffic Flow
There is no input like:
My acc code don't care about this.... ![:)](./images/smilies/icon_smile.gif)
Code: Select all
1
1 3
0 0 950
0 0 800
0 0 900
![:)](./images/smilies/icon_smile.gif)