CCF 2018-12-4 数据中心 100分

/*---克鲁斯卡尔算法---*/
//其实题意就是找最小生成树中的最大的边 
#include<iostream>
#include<algorithm>
using namespace std;const int MAXV=50001;//最大顶点数 
const int MAXE=100001;struct edge{//边的结构体 int u,v;int cost;
}E[MAXE];bool cmp(edge a,edge b){return a.cost<b.cost;
}int father[MAXV];//并查数组集 
int findFather(int x){//并查集查询函数 int a=x;while(x!=father[x]){x=father[x];}//路径压缩 while(a!=father[a]){int z=a;a=father[a];father[z]=x;}return x;
}
//克鲁斯卡尔部分，返回最小生成树的边权之和，n个顶点，m条边 
int kruskal(int n,int m){//ans为生成树权值，Num_Edge为生成树的边数 int ans=0,Num_Edge=0;for(int i=1;i<=n;i++){//顶点范围从1--n father[i]=i;//并查集初始化 }sort(E,E+m,cmp);for(int i=0;i<m;i++){//枚举所有边 int faU=findFather(E[i].u);//查询测试两个端点所在集合的根节点 int faV=findFather(E[i].v);if(faU!=faV){//若不在一个集合中 father[faU]=faV;//合并集合 if(E[i].cost>ans)ans=E[i].cost; //使ans变成最大的边 Num_Edge++;//边数+1 if(Num_Edge==n-1)break;//边数等于顶点数-1时跳出 }}if(Num_Edge!=n-1)return -1;else return ans;
}int main(){int n,m;int u,v,w,s; cin>>n>>m>>s;for(int i=0;i<m;i++){//输入图 cin>>E[i].u>>E[i].v>>E[i].cost;}int ans=kruskal(n,m);cout<<ans;
}

更多相关CCF的试题解答，请点击>>CCF历年认证考试解答