首页 > 代码库 > hdu 2485 Highways
hdu 2485 Highways
题意:Flatopia岛要修路,这个岛上有n个城市,要求修完路后,各城市之间可以相互到达,且修的总
路程最短.
求所修路中的最长的路段
最小生成树的一道题,很裸的一道题,不知道为什么就是编译过不了。
#include<iostream>#include<cstdlib>#include<cstring>#include<algorithm>using namespace std;int w[200000],u[200000],v[200000],p[510],r[200000];int cmp(const int i,const int j){ return w[i]<w[j];}int find(int x){ return p[x] == x? x:find(p[x]);}int main(){ int a; cin >> a; while(a--) { memset(w,200000,0); memset(u,200000,0); memset(v,200000,0); int b; cin >> b; int temp =0,count = 1; for(int i =1; i<= b;i++) { for(int j = 1; j<= i;j++) { cin >> temp; } for(int j = i+1;j<= b;j++) { u[count] = i; v[count] = j; cin >> w[count++]; //cout<< w[count-1]<< endl; } } int ans = 0; for(int i = 0; i< 510;i++) { p[i] = i; } for(int i =0; i <= b;i++) { r[i] = i; } sort(r+1,r+b+1,cmp); /*for(int i = 1; i <= 3;i++) cout<< w[r[i]]<< endl;*/ for(int i = 1;i<= b;i++) { int e = r[i]; int x= find(u[e]); int y = find(v[e]); if(x!= y) { ans = w[e]; p[x] = y; } } cout<< ans << endl; } return 0;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。