首页 > 代码库 > hdu 2485 Highways

hdu 2485 Highways

2024-07-14 04:26:46   224人阅读

题意: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;}

　　


联系
我们