求助没过点!(急)
查看原帖
求助没过点!(急)
494699
卷王慢即快楼主2023/1/9 15:50
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct node
{
	int u, v;
	ll w;
}e[300005];
int n, tot = 0, cnt = 0, num = 0;
int x[2001], y[2001];
int c[2001], k[2001], f[2001];
int st[2001], top = 0;
int t[2][2001];
ll ans = 0;
inline bool cmp(node x, node y)
{
	return x.w < y.w;
}
inline int find(int x)
{
	if(f[x] == x) return x;
	return f[x] = find(f[x]);
}
inline ll dis(int i, int j)
{
	return pow(x[i] - x[j], 2) + pow(y[i] - y[j], 2);
}
inline int read()
{
	int x = 0, f = 1;
	char ch = getchar();
	while(ch < '0' || ch > '9')
	{
		if(ch == '-') f = -1;
		ch = getchar();
	}
	while(ch >= '0' && ch <= '9')
	{
		x = (x << 1) + (x << 3) + (ch ^ 48);
		ch = getchar();
	}
	return x * f;
}
int main()
{
	n = read();
	for(int i = 1; i <= n; i++)
		f[i] = i;
	for(int i = 1; i <= n; i++)
		x[i] = read(), y[i] = read();
	for(int i = 1; i <= n; i++)
	{
		c[i] = read();
		e[++cnt] = (node){0, i, c[i]};
	}
	for(int i = 1; i <= n; i++)
		k[i] = read();
	for(int i = 1; i < n; i++)
		for(int j = i + 1; j <= n; j++)
			e[++cnt] = (node){i, j, (ll)(k[i] + k[j]) * dis(i, j)};
	sort(e + 1, e + cnt + 1, cmp);
	for(int i = 1; i <= cnt; i++)
	{
		int u = find(e[i].u), v = find(e[i].v);
		if(u == v) continue;
		f[u] = v; tot++;
		ans += e[i].w;
		if(!e[i].u) st[++top] = e[i].v;
		else
		{
			t[0][++num] = e[i].u;
			t[1][num] = e[i].v;
		}
		if(tot == n) break;
	}
	printf("%d\n%d\n", ans, top);
	for(int i = 1; i <= top; i++)
		printf("%d ", st[i]);
	printf("\n%d\n", num);
	for(int i = 1; i <= num; i++)
		printf("%d %d\n", t[0][i], t[1][i]);
	return 0;
}
2023/1/9 15:50
加载中...