救救孩子吧
  • 板块灌水区
  • 楼主The_End_of_GCC
  • 当前回复8
  • 已保存回复8
  • 发布时间2024/7/14 08:54
  • 上次更新2024/7/14 10:28:43
查看原帖
救救孩子吧
671415
The_End_of_GCC楼主2024/7/14 08:54

昨天比赛div2的第四题,我想骗40分,然而因为1个点RE导致我一分没拿。

求大佬指出问题。会给大佬2个关注的。

#include<bits/stdc++.h>
using namespace std;
long long f[3000100]={0},waycount=0,s=0,use=0,fa[3000010]={0};
long long qw[3000100]={0},er[3000100]={0},qwer,idx,vis[3000100]={0};
long long n,m;
struct ff
{
	long long u,v,w;
}way[3000100];
long long find(long long x)
{
	if(fa[x]==x)
		return x;
	return fa[x]=find(fa[x]); 
}
bool cmp(ff x,ff y)	{return x.w<y.w;}
long long fff()
{
	for(long long i=1;i<=waycount;i++)
	{
		long long q=find(way[i].u),w=find(way[i].v);
		if(q==w)
			continue;
		s+=way[i].w;
		fa[q]=w;
		use++;
		vis[i]=1;
		qw[use]=way[i].u;
		er[use]=way[i].v;
		if(use==n-1)
		{
			qwer=use;
			if(use==m) 
				return 0;
			long long idx=0;
			for(long long j=1;j<=waycount;j++)
			{
				if(vis[j]==0)
				{
					s+=way[j].w;
					qwer++;
					qw[qwer]=way[j].u;
					er[qwer]=way[j].v;
					idx++;
					if(idx+use==m)
						break;
				}
			}
			return 0;
		}
	}
}
int main()
{
	
	cin>>n>>m;
	for(long long i=1;i<=n;i++)
		cin>>f[i],fa[i]=i;
	for(long long i=1;i<n;i++)
	{
		for(long long j=i+1;j<=n;j++)
		{
			waycount++;
			way[waycount].u=i;
			way[waycount].v=j;
			way[waycount].w=f[i]*f[j];
		}
	}
	sort(way+1,way+waycount+1,cmp);
	fff();

	cout<<s<<endl;
	for(long long i=1;i<=m;i++)
		cout<<qw[i]<<" "<<er[i]<<endl;
	cout<<endl;
	return 0;
}
2024/7/14 08:54
加载中...