求助
查看原帖
求助
831702
_mortal_楼主2023/5/30 23:50
#include<bits/stdc++.h>
using namespace std;

int n;
int fa[2010];//并查集
inline int find(int n)
{
	return fa[n]==n?n:fa[n]=find(fa[n]);
}
void merge(int x,int y)
{
	fa[find(x)]=find(y);
}
struct node{
	int x,y,c,k;
}a[2010];//城市
struct way{
	int x,y,w;
	friend bool operator < (way x,way y)
	{
		return x.w<y.w;
	}
}edge[6000007];//边
int cnt;
void add_edge(int x,int y,int w)
{
	edge[++cnt]=(way){x,y,w};
}
long long res,tot;
vector<int>build_ele;
vector<pair<int,int> >line;
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d%d",&a[i].x,&a[i].y);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i].c);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i].k);
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			add_edge(i,j,(a[i].k+a[j].k)*(abs(a[i].x-a[j].x)+abs(a[i].y-a[j].y)));
		}
		add_edge(0,i,a[i].c);
	}
	sort(edge+1,edge+1+cnt);
	for(int i=0;i<=n;i++)
		fa[i]=i;
	for(int i=1;i<=cnt&&tot<=n;i++)
	{
		int x=edge[i].x,y=edge[i].y,w=edge[i].w;
		if(find(x)==find(y))continue;
		// 建发电站
		if(x==0)
		{
			build_ele.push_back(y);
		}
		else
		{
			line.push_back(make_pair(x,y));
		}
		merge(x,y);
		res+=w;
		tot++;

	}
	cout<<res<<'\n';
	cout<<build_ele.size()<<'\n';
	for(int i=0;i<build_ele.size();i++)
		cout<<build_ele[i]<<' ';
	cout<<'\n';
	cout<<line.size()<<'\n';
	for(int i=0;i<line.size();i++)
		cout<<line[i].first<<' '<<line[i].second<<'\n';
	return 0;
}

第四个点一直过不了/kk(验证码 91fw,大怒)

2023/5/30 23:50
加载中...