求助,过了三个测试点
查看原帖
求助,过了三个测试点
561949
syr1125楼主2024/5/9 10:47
#include <bits/stdc++.h>
using namespace std;

struct node
{
	int x, y;
}a[2005];

int f[2005];

struct edge
{
	int x, y;
	long long z;
	
	bool operator < (const edge __) const
	{
		return z < __.z;
	}
}edge[4000005];

int find(int x)
{
	if (f[x] != x)
	{
		f[x] = find(f[x]);
	}
	return f[x];
}

int n, m, c[2005], k[2005];

vector<int> ele, con;

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", &c[i]);
	}
	for (int i = 1; i <= n; i ++)
	{
		scanf("%d", &k[i]);
	}
	for (int i = 1; i <= n; i ++)
	{
		for (int j = i + 1; j <= n; j ++)
		{
			edge[++ m] = {i, j, (k[i] + k[j]) * (abs(a[i].x - a[j].x) + abs(a[i].y - a[j].y))};
		}
	}
	
	for (int i = 1; i <= n; i ++)
	{
		edge[++ m] = {i, 0, c[i]}; 
	}
	
	sort(edge + 1, edge + 1 + m);
	for (int i = 0; i <= n; i ++) 
	{
		f[i] = i;
	}
	
	long long ans = 0;
	for (int i = 1; i <= m; i ++)
	{
		int _x = edge[i].x, _y = edge[i].y;
		long long _z = edge[i].z;
		int a1 = find(_x), b1 = find(_y);
		if (a1 == b1)
		{
			continue;
		}
		if (_x == 0 || _y == 0)
		{
			ele.push_back(_x ^ _y);
		}
		else
		{
			con.push_back(_x), con.push_back(_y);
		}
		f[a1] = b1;
		ans += _z;
	}
	printf("%lld\n", ans);
	printf("%d\n", ele.size());
	for (int i = 0; i < ele.size(); i ++) printf("%d ", ele[i]);
	puts(" ");
	printf("%d\n", con.size() / 2);
	for (int i = 0; i < con.size(); i ++)
	{
		if (i % 2 == 0) printf("%d ", con[i]);
		else printf("%d\n", con[i]);
	}
	return 0;
}

2024/5/9 10:47
加载中...