题目描述
blablabla
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e5+10,M=2*N;
int sum=0;
struct Edge
{
int a,b,w;
bool operator< (const Edge &W) const
{
return w<W.w;
}
}edge[M];
int p[N],n,m,cnt;
int find(int x)
{
if(p[x]!=x)p[x]=find(p[x]);
return p[x];
}
int kruskal()
{
sort(edge,edge+m);
for(int i=0;i<m;i++)
{
int a=edge[i].a,b=edge[i].b,w=edge[i].w;
int pa=find(a),pb=find(b);
if(pa!=pb)
{
cnt++;
p[pa]=pb; //必须要p[pa]=pb 不能p[a]=pb因为pa为祖宗节点,如果让p[a]改变,那么其他节点就可能更新不了(比如他的父节点)
sum+=w;
}
}
if(cnt==n-1) return sum;
else return -1;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=0;i<m;i++)
{
int a,b,w;
scanf("%d%d%d",&a,&b,&w);
edge[i]={a,b,w};
}
for(int i=1;i<=n;i++) p[i]=i;
int tmp=kruskal();
if(tmp==-1) printf("impossible\n");
else printf("%d\n",tmp);
return 0;
}
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla