Kruskal,0分TLE求助P2330
  • 板块题目总版
  • 楼主T20201126
  • 当前回复3
  • 已保存回复3
  • 发布时间2022/7/4 16:15
  • 上次更新2023/10/27 21:54:18
查看原帖
Kruskal,0分TLE求助P2330
419474
T20201126楼主2022/7/4 16:15
#include<bits/stdc++.h>
using namespace std;
const int N=400;
long long n,m,f[N],maxx,cnt;
struct node
{
   long long from,to,w;
   bool operator < (const node &b)const
   {
       w<b.w;
   }
}edge[200520];
long long find(long long x)
{
   return f[x]!=x?f[x]=find(f[x]):x;
}
void add(long long x,long long y)
{
   long long fx=find(x);
   long long fy=find(y);
   if(fx!=fy)
       f[fx]=f[fy];
   return ;
}
void kruskal()
{
   for(int i=1;i<=m;++i) 
   {
       long long fa=find(edge[i].from);
       long long fb=find(edge[i].to);
       if(fa!=fb)
       {
           add(fa,fb);
           ++cnt;
           maxx=edge[i].w;
       }
       if(cnt==n-1) break;
   }
   cout<<n-1<<' '<<maxx;
   return ;
}
int main()
{
   cin>>n>>m;
   for(int i=1;i<=m;++i)
   {
       long long  o,p,q;
       cin>>o>>p>>q;
       edge[i]={o,p,q};
   }
   sort(edge+1,edge+1+m);
   for(int i=1;i<=n;++i) f[i]=i;
   kruskal();
   return 0;
}
2022/7/4 16:15
加载中...