关于最小生成树,Kruskal算法
查看原帖
关于最小生成树,Kruskal算法
178195
人间温柔楼主2020/6/25 12:48

题目传送门

最近在做的一道题,关于最小生成树的,我用到的是KruskalKruskal算法,但是为什么样例都过不了?

输入是复制的,没问题。标准输出是176176,我的输出是66

#我的代码:

#include<bits/stdc++.h>
using namespace std;

struct edge{
	int s,e,l;
}a[100005];
int n,p;
int minn=INT_MAX;
int c[10005];
int pa[10010];
int ans=0;

bool cmp(const edge &x,const edge &y)
{
	return x.l < y.l;
}

bool find(int u)
{
	if(u==pa[u]) return u;
	return pa[u]=find(pa[u]);
}


int main()
{
	cin>>n>>p;
	for(int i=0;i<n;i++)
	{
		cin>>c[i];
		minn=min(minn,c[i]);
	}
	for(int i=0;i<p;i++)
	{
		int ss,ee,ll;
		cin>>ss>>ee>>ll;
		a[i].s=ss;
		a[i].e=ee;
		a[i].l=2*ll+c[ss]+c[ee];
	}
	sort(a,a+p,cmp);
	for(int i=1;i<=n;i++)
	{
		pa[i]=i;
	}
	for(int i=0;i<p;i++)
	{
		int u=a[i].s;
		int v=a[i].e;
		if(find(u)!=find(v))
		{
			pa[u]=v;
			ans+=a[i].l;
		}
	}
	cout<<ans+minn;
	return 0;
}
2020/6/25 12:48
加载中...