题目描述
blablabla
样例
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=200010,M=200010;
int n,m;
struct Edge{
int u,v,w;
}edges[M];
int p[N];
bool cmp(Edge a,Edge b)
{
return a.w<b.w;
}
int find(int x)
{
if(x!=p[x]) p[x]=find(p[x]);
return p[x];
}
int main()
{
cin>>n>>m;
int u,v,w;
for(int i=0;i<m;i++)
{
cin>>u>>v>>w;
edges[i]={u,v,w};
}
for(int i=1;i<=n;i++) p[i]=i;
sort(edges,edges+m,cmp);
int cnt=0;
int res=0;
for(int i=0;i<m;i++)
{
int a=edges[i].u;
int b=edges[i].v;
int w=edges[i].w;
// a=find(a);
// b=find(b);
if(find(a)!=find(b))
{
p[a]=b;
cnt+=1;
res+=w;
}
}
if(cnt<n-1) cout<<"impossible"<<endl;
else cout<<res<<endl;
}
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla