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;
}