求助只过了12个点
查看原帖
求助只过了12个点
195198
E1_de5truct0r楼主2021/5/22 13:31

RT,不知道哪里错了(

#include <bits/stdc++.h>
#define int long long
using namespace std;
int read()
{
	int w=0,f=1;char ch=getchar();
	for(;!isdigit(ch);ch=getchar()) if(ch=='-')f=-1;
	for(;isdigit(ch);ch=getchar()) w=(w<<1)+(w<<3)+(ch^48);
	return w*f;
}
int n,tot=0;

struct city{int x,y,c,k,id;}a[2005];
struct Edge
{
	int from,to,w;
	bool flag;
	Edge(int x,int y,int z,bool hack)
	{
		from=x;
		to=y;
		w=z;
		flag=hack;
	}
	Edge(){}
	bool operator<(const Edge &x)const
	{
		return w<x.w;
	}
}E[4000005];
struct Node{int a,b;}ans[4000005];
int ele[4000005],fa[2005];

inline int man(int ax,int ay,int bx,int by)
{
	return abs(ax-bx)+abs(ay-by);
}
int findfa(int k)
{
	if(fa[k]==k) return k;
	return fa[k]=findfa(fa[k]);
}
signed main()
{
	n=read();
	for(register int i=1;i<=n;i++)
		a[i].x=read(),a[i].y=read();
	for(register int i=1;i<=n;i++)
		a[i].c=read();
	for(register int i=1;i<=n;i++)
		a[i].k=read();
	for(register int i=1;i<=n;i++)
		for(register int j=i+1;j<=n;j++)
		{
			int MANN=man(a[i].x,a[i].y,a[j].x,a[j].y);
			Edge tmp1(i,j,MANN*(a[i].k+a[j].k),0);
			E[++tot]=tmp1;
		}
	for(register int i=1;i<=n;i++)
	{
		Edge tmp2(0,i,a[i].c,1);
		E[++tot]=tmp2;
	}
	
	for(register int i=1;i<=n;i++)
		fa[i]=i;
	
	sort(E+1,E+tot+1);
	int mindis=0,LENANS,LENELE,FUCK=1,i;
	LENANS=LENELE=i=0;
	while(FUCK<=n && i<=tot)
	{
		i++;FUCK++;
		int x=E[i].from,y=E[i].to;
		if(findfa(x)==findfa(y)) continue;
		if(E[i].flag==0)
		{
			Node sb;
			sb.a=x;sb.b=y;
			ans[++LENANS]=sb;
		}
		else ele[++LENELE]=y;
		mindis+=E[i].w;
		fa[x]=y;
	}
	printf("%lld\n",mindis);
	printf("%lld\n",LENELE);
	for(register int i=1;i<=LENELE;i++)
		printf("%lld ",ele[i]);
	if(LENELE!=0) putchar('\n');
	printf("%lld\n",LENANS);
	for(register int i=1;i<=LENANS;i++)
		printf("%lld %lld\n",ans[i].a,ans[i].b);
	return 0;
}
2021/5/22 13:31
加载中...