85分悬关求调
查看原帖
85分悬关求调
752711
hateful_bug楼主2024/6/2 13:00
#include<bits/stdc++.h>
using namespace std;
long long n,xzb[2000005],yzb[2000005],tt,w[2000005],k[2000005],f[2000005],ans,fdz[2000005],dx[2000005][2],tt1,tt2;
struct jgt
{
	long long x;
	long long y;
	long long z;
}a[2000005];
bool cmp(jgt a,jgt b)
{
	return a.z<b.z;
}
long long cx(long long x)
{
	if(x==f[x])
	return x;
	return f[x]=cx(f[x]);
}
int main()
{
	scanf("%lld",&n);
	for(int i=1;i<=n;i++)
	f[i]=i;
	for(int i=1;i<=n;i++)
	scanf("%lld%lld",&xzb[i],&yzb[i]);
	for(int i=1;i<=n;i++)
	scanf("%lld",&w[i]),a[++tt].x=i,a[tt].y=0,a[tt].z=w[i];//long long(w[i]);
	for(int i=1;i<=n;i++)
	scanf("%lld",&k[i]);
	for(int i=1;i<=n;i++)
	for(int j=1;j<i;j++)
	{
		a[++tt].x=i;
		a[tt].y=j;
		a[tt].z=(k[i]+k[j])*(abs(xzb[i]-xzb[j])+abs(yzb[i]-yzb[j]));
	}
	sort(a+1,a+tt+1,cmp);
	for(int i=1;i<=tt;i++)
	{
		int x1=a[i].x,y1=a[i].y,z1=a[i].z;
		if(cx(x1)==cx(y1))
		continue;
		f[cx(x1)]=cx(y1);
		ans+=z1;
		if(x1==0||y1==0)
		fdz[++tt1]=max(x1,y1);
		else
		dx[++tt2][0]=x1,dx[tt2][1]=y1;
	}
	printf("%lld\n%lld\n",ans,tt1);
	for(int i=1;i<=tt1;i++)
	printf("%lld ",fdz[i]);
	printf("\n%lld\n",tt2);
	for(int i=1;i<=tt2;i++)
	printf("%lld %lld\n",dx[i][0],dx[i][1]);
	return 0;
}
2024/6/2 13:00
加载中...