首页 > 代码库 > [POJ2485]Highways

[POJ2485]Highways

2024-09-24 01:24:05   203人阅读

题目大意：Flatopia岛要修路,这个岛上有n个城市,要求修完路后,任意城市都可以到达其他城市,且修的总长度最短。

解题思路：很明显裸的最小生成树，只不过是求最大的边的权值。我用的是Kruskal。

（注意：请用“C++”提交，“G++”会超时）

 

 1 #include<algorithm> 2 #include<cstdio> 3 #include<cstring> 4 using namespace std; 5 struct bian{ 6     int u,v,d; 7     bool operator <(const bian& rhs)const{return d<rhs.d;} 8 }a[500*500+25]; 9 int m=0,n,dad[505],s;10 int fa(int x){11     return(dad[x]==x)?(x):(dad[x]=fa(dad[x]));12 }13 int main(){14     scanf("%d",&s);15     while(s--){16         memset(a,0,sizeof(a));17         scanf("%d",&n);18         for(int i=1;i<=n;i++)19         for(int j=1;j<=n;j++){20             int x;21             scanf("%d",&x);22             if(x!=0){23                 m++;24                 a[m].u=i,a[m].v=j,a[m].d=x;25             }26         }27         sort(a+1,a+m+1);28         for(int i=1;i<=n;i++)dad[i]=i;29         int now=0,T=1;30         while(T!=n){31             now++;32             int x=fa(a[now].u),y=fa(a[now].v);33             if(x!=y){34                 dad[y]=x;35                 T++;36                 if(T==n){//排过序后最后一个就是最大的。37                     printf("%d\n",a[now].d);38                 }39             }40         }41     }42     return 0;43 }

 

 

 

[POJ2485]Highways


联系
我们