wa*23 求助
查看原帖
wa*23 求助
66964
heyuguo楼主2024/4/28 21:21
#include<bits/stdc++.h>
using namespace std;
long long n,m,a[200005],fa[200005],mina[200005],mini[200005],ans,cnt,b[200005],t;
map<long long,bool> p;
long long getf(long long x)
{
	while(x!=fa[x])x=fa[x]=fa[fa[x]];
	return x;
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		fa[i]=i;
	}
	for(int i=1;i<=m;i++)
	{
		long long u,v;
		cin>>u>>v;u++,v++;
		fa[u]=getf(u);
		fa[v]=getf(v);
		fa[fa[u]]=fa[v];
	}
	memset(mina,0x3f,sizeof mina);
	for(int i=1;i<=n;i++)
	{
		fa[i]=getf(i);
		if(mina[fa[i]]>a[i])
		{
			mina[fa[i]]=a[i];
			mini[fa[i]]=i;
		}
	}
	
	for(int i=1;i<=n;i++)
	{
		if(mini[i]!=0)
		{
			ans+=mina[i];
			p[mini[i]]=1;
			cnt++;
		}
	}
	if(cnt==1)
	{
		cout<<0;
		return 0;
	}
	if(cnt*2-2>n)
	{
		cout<<"Impossible";
		return 0;
	}
	for(int i=1;i<=n;i++)
	{
		if(p.end()!=p.find(i))
		{
			b[++t]=a[i];
		}
	}
	sort(b+1,b+1+t);
	for(int i=1;i<=cnt-2;i++)
		ans+=b[i];
	cout<<ans;
	return 0;
}
2024/4/28 21:21
加载中...