CCF 认证 201812-4 数据中心（100分） - 好文

CCF 认证 201812-4 数据中心（100分）

被12月CCF认证的成绩打击了好久之后，官网出题之后，对自己第四题不相信0分，注释了freopen之后交了一次。100分。

这就非常扎心了。但是还是给了我信心，至少刷题没有白费功夫，还是太粗心了。下次继续！！！

题编号： 201812-4
试题名称：数据中心
时间限制： 1.0s
内存限制： 512.0MB
问题描述：

样例输入

4
5
1
1 2 3
1 3 4
1 4 5
2 3 8
3 4 2

样例输出

4

样例说明

　　下图是样例说明。

思路：已经不记得了，但是就是个kruscal的板子题。
#include<cstdio> #include<iostream> #include<cstring> #include<algorithm>
#include<queue> using namespace std; //min tree--maxn const int maxn=5*1e5+10;
int f[maxn]; struct edge{ int u,v,w; bool operator <(const edge &u)const {
return w<u.w; } }edge[2*maxn]; int tot; void addedge(int u,int v,int w) {
edge[tot].u=u; edge[tot].v=v; edge[tot++].w=w; } int find(int x) { return
f[x]==-1?x:f[x]=find(f[x]); } int kruskal(int n) { memset(f,-1,sizeof(f));
sort(edge,edge+tot); int cnt=0,ans=-1; for(int i=0;i<tot;i++) { int
u=edge[i].u; int v=edge[i].v; int w=edge[i].w; int t1=find(u); int t2=find(v);
if(t1!=t2) { //ans+=w; f[t1]=t2; ans=max(w,ans); cnt++; } if(cnt==n-1) break; }
return ans; } int main() { int n,m,root; int u,v,w; tot=0;
//freopen("in.txt","r",stdin); scanf("%d%d%d",&n,&m,&root); for(int
i=0;i<m;i++) { scanf("%d%d%d",&u,&v,&w); addedge(u,v,w); addedge(v,u,w); }
printf("%d\n",kruskal(n)); return 0; }

热门工具换一换