一个玄学疑惑
查看原帖
一个玄学疑惑
342316
yiming_328楼主2024/4/5 21:51

为什么这样过了↓

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const int N=1e5+5;
ll n,k,f[N];
ll ans=0;
bool ofa[4*N];//occupy from army
struct road
{
	int from,to;
	ll way;
	bool operator<(const road &x)const
	{
		return way>x.way;
	}
}s[4*N];
inline ll read()
{
	ll r=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9')
	{
		if(c=='-') f=-f;
		c=getchar();
	}
	while(c>='0'&&c<='9')
	{
		r=(r<<1)+(r<<3)+(c^48);
		c=getchar();
	}
	return r*f;
}
inline void write(ll x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>=10) write(x/10);
	putchar(x%10+'0');
}
inline ll find(ll x)
{
	if(f[x]==x) return x;
	return f[x]=find(f[x]);
}
signed main()
{
	n=read();k=read();
	for(register int i=1;i<=n;++i)
		f[i]=i;
	for(register int i=1;i<=k;++i)
	{
		ll x=read();
		ofa[x]=true;
	}
	for(register int i=1;i<=n-1;++i)
	{
		s[i].from=read();
		s[i].to=read();
		s[i].way=read();
		ans+=s[i].way;
	}
//	cout<<ans<<endl;
	sort(s+1,s+1+n);
	for(register int i=1;i<=n-1;++i)
	{
		int a=s[i].from,b=s[i].to;
		int fa=find(a),fb=find(b);
		if(ofa[fa]&&ofa[fb])
			continue;
		f[fa]=fb;
		ans-=s[i].way;
		if(ofa[fa]) ofa[fb]=true;
		else ofa[fa]=true;
//		ofa[fa]=true;
//		ofa[fb]=true;
	}
	write(ans);
	return 0;
}

而这样↓就不行

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const int N=1e5+5;
ll n,k,f[N];
ll ans=0;
bool ofa[4*N];//occupy from army
struct road
{
	int from,to;
	ll way;
	bool operator<(const road &x)const
	{
		return way>x.way;
	}
}s[4*N];
inline ll read()
{
	ll r=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9')
	{
		if(c=='-') f=-f;
		c=getchar();
	}
	while(c>='0'&&c<='9')
	{
		r=(r<<1)+(r<<3)+(c^48);
		c=getchar();
	}
	return r*f;
}
inline void write(ll x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>=10) write(x/10);
	putchar(x%10+'0');
}
inline ll find(ll x)
{
	if(f[x]==x) return x;
	return f[x]=find(f[x]);
}
signed main()
{
	n=read();k=read();
	for(register int i=1;i<=n;++i)
		f[i]=i;
	for(register int i=1;i<=k;++i)
	{
		ll x=read();
		ofa[x]=true;
	}
	for(register int i=1;i<=n-1;++i)
	{
		s[i].from=read();
		s[i].to=read();
		s[i].way=read();
		ans+=s[i].way;
	}
//	cout<<ans<<endl;
	sort(s+1,s+1+n);
	for(register int i=1;i<=n-1;++i)
	{
		int a=s[i].from,b=s[i].to;
		int fa=find(a),fb=find(b);
		if(ofa[fa]&&ofa[fb])
			continue;
		f[fa]=fb;
		ans-=s[i].way;
//		if(ofa[fa]) ofa[fb]=true;
//		else ofa[fa]=true;
		ofa[fa]=true;
		ofa[fb]=true;
	}
	write(ans);
	return 0;
}
2024/4/5 21:51
加载中...