水题之王SP…这题就裸的最小生成树
/**************************************************************
Problem: 1083
User: zhuohan123
Language: C++
Result: Accepted
Time:32 ms
Memory:1404 kb
****************************************************************/ #include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
struct edge
{
int u,v,c;
friend bool operator<(edge a,edge b){return a.c<b.c;}
}g[];
int f[];
int gf(int p){return f[p]==p?p:f[p]=gf(f[p]);}
int main(int argc, char *argv[])
{
int n,m;scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)f[i]=i;
for(int i=;i<=m;i++)scanf("%d%d%d",&g[i].u,&g[i].v,&g[i].c);
sort(g+,g+m+);
int bmax=;
for(int i=;i<=m;i++)
if(gf(g[i].u)!=gf(g[i].v))
{
bmax=g[i].c;
f[gf(g[i].u)]=gf(g[i].v);
}
printf("%d %d\n",n-,bmax);
return ;
}