[第15次CCFCSP]数据中心

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
int cnt=0,ans=0;
int head[N];
int n,m,root;
int maxx=-1;
struct node
{
int u;
int v;
int w;
}edge[N];

int father[N];
void init()
{
for(int i=1;i<=N;i++)
{
father[i]=i;
}
}
int find_set(int n)
{
return father[n]==n?n:(father[n]=find_set(father[n]));
}
void union_set(int a,int b)
{
int x=find_set(a);
int y=find_set(b);
if(a!=b)
{
father[b]=a;
}
}
bool cmp(node a,node b)
{
return a.w<b.w;
}
void kruskal()
{
sort(edge+1,edge+1+m,cmp);
for(int i=1;i<=m;i++)
{
if(cnt==n-1)break;
int a=find_set(edge[i].u);
int b=find_set(edge[i].v);
if(a==b)continue;
else
{
father[b]=a;
cnt++;
ans+=edge[i].w;
maxx=max(maxx,edge[i].w);
} 
}
}
int main()
{
cin>>n>>m>>root;
for(int i=1;i<=m;i++)
{
int u,v,w;
cin>>edge[i].u>>edge[i].v>>edge[i].w;
}
init();
kruskal();
cout<<maxx;
return 0;
}

        通过kruskal算法求出最短路，在把符合条件的边加入总值时每次比较maxx更新最大值，输出即可。

        模板题

原文地址：https://blog.csdn.net/flyidj/article/details/144022787

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！