玄学MLE 20pts
查看原帖
玄学MLE 20pts
750841
jorrunur_jorisuesk楼主2024/10/2 21:00

思路是找最大的不与敌方点相连(我方点不一定联通)的所有连边,然后总边权值-找到的边权值=删掉的最小边

好像是并查集的一些操作引起的,有问题的地方找到了,但不知道怎么解决:

#include<bits/stdc++.h>
using namespace std;
int n,k;
struct Edge{
	long long w,to,pre;
}edge[100100];
bool enemy[100100];
int fa[100100];
bool cmp(Edge a,Edge b)
{
	return a.w>b.w;
}
long long find(int k)
{
	if(fa[k]!=k)
	fa[k]=find(k);
	return fa[k];
}
int main()
{
	cin>>n>>k;
	long long total=0;
	for(int i=0;i<k;i++)
	{
		int t;
		cin>>t;
		enemy[t]=1;
	}
	for(int i=0;i<n;i++)
	fa[i]=i;
	for(int i=0;i<n-1;i++)
	{
		int a,b,c;
		cin>>a>>b>>c;
		edge[i].pre=a;
		edge[i].to=b;
		edge[i].w=c;
		total+=c;
	}
	sort(edge,edge+n-1,cmp);
	long long ans=0;
	for(int i=0;i<n-1;i++)
	{
		bool A,B;
		A=enemy[find(edge[i].pre)];
		B=enemy[find(edge[i].to)];
      //这段以下有问题
		if(!A||!B)
		{
			if(A&&!B)
			fa[find(edge[i].to)]=find(edge[i].pre);
			else if(B&&!A)
			fa[find(edge[i].pre)]=find(edge[i].to);
			ans+=edge[i].w;
		}
      //这段以上有问题
	}
	cout<<total-ans;
	return 0;
}
2024/10/2 21:00
加载中...