【vijos】P1190 繁忙的都市

【算法】最小生成树

#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=310;
struct cyc{int from,to,pre,k;}e[100010];
int fa[maxn],head[maxn],n,m,cnt,tot,maxs;
bool cmp(cyc a,cyc b){return a.k<b.k;}
void insert(int u,int v,int k)
{cnt++;e[cnt].from=u;e[cnt].to=v;e[cnt].pre=head[u];head[u]=cnt;e[cnt].k=k;}
int getfa(int x)
{return fa[x]==x?x:(fa[x]=getfa(fa[x]));}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
     {
         int u,v,c;
         scanf("%d%d%d",&u,&v,&c);
         insert(u,v,c);
         insert(v,u,c);
     }
    sort(e+1,e+cnt+1,cmp);
    for(int i=1;i<=n;i++)fa[i]=i;
    tot=0;
    for(int i=1;i<=cnt;i++)
     {
         int u=e[i].from,v=e[i].to;
         if(getfa(u)!=getfa(v))
          {
              fa[fa[u]]=fa[v];
              tot++;maxs=e[i].k;
          }
         if(tot>=n-1)break;
     }
    printf("%d %d",tot,maxs);
    return 0;
}