用kruskal空间炸了,求助!
查看原帖
用kruskal空间炸了,求助!
374347
Wander_E楼主2023/7/21 20:05
#include <bits/stdc++.h>
#define int	long long
using namespace std;

const int N = 4e6 + 500;
const int INF = 1e7;
int n, m;
int a[N];
int c[N];
int k[N];
int px[N], py[N];
int ans2 = 0; // 2
int ans3[N], cur = 0;// 3
int ans4[N], idx = 0;// 4

struct Node
{
	int x, y, z;
}e[N]; 

void init()
{
	for(int i = 0; i <= n; i++)
		a[i] = i;
}

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

int krus()
{
	int ans = 0, cnt = 1;
	for(int i = 1; i <= m; i++)
	{
		int x = find(e[i].x);
		int y = find(e[i].y);
		if(x != y)
		{
			cnt++;
			ans += e[i].z;
			if(e[i].x == n || e[i].y == n) 
			{
				ans2++;
				ans3[++cur] = (e[i].x == n? e[i].y : e[i].x);
			}
			else ans4[++idx] = i;
			if(cnt == n) return ans;
			a[x] = y;
		}
	}
	return -1;
}

bool cmp(Node a, Node b)
{
	return a.z < b.z;
}

signed main()
{
	cin >> n;
	init();
	for(int i = 1; i <= n; i++)
		cin >> px[i] >> py[i];
	for(int i = 1; i <= n; i++) cin >> c[i];
	for(int i = 1; i <= n; i++) cin >> k[i];
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= n; j++)
		{
			if(i == j) continue;
			e[++m].x = i;
			e[m].y = j;
			e[m].z = (abs(px[i] - px[j]) + abs(py[i] - py[j])) * (k[i] + k[j]);
		}
	for(int i = 1; i <= n; i++)
	{
		e[++m].x = i;
		e[m].y = n + 1;
		e[m].z = c[i];
		e[++m].x = n + 1;
		e[m].y = i;
		e[m].z = c[i];
	}
	n++;
	sort(e + 1, e + m + 1, cmp);
	int num = krus();
	if(num == -1) cout << "-1" << endl;
	else cout << num << endl;
	cout << ans2 << endl;
	for(int i = 1; i <= cur; i++) cout << ans3[i] << ' ';
	cout << endl;
	cout << idx << endl;
	for(int i = 1; i <= idx; i++) 
	{
		if(e[ans4[i]].x == e[ans4[i]].y) continue;
		cout << e[ans4[i]].x << ' ' << e[ans4[i]].y << endl;
	}
	return 0;
}
2023/7/21 20:05
加载中...