为什么只有我WA on #7?
查看原帖
为什么只有我WA on #7?
326254
LonginusMonkey楼主2024/8/4 00:37

开longlong了

#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int maxn = 2010, maxm = 2000100;

int x[maxn], y[maxn], c[maxn], k[maxn];
struct node{
	int from, to, w, bl;
	bool operator<(node b) {
		return w < b.w;
	}
}edge[maxm];

long long cnt;
int fa[maxn];
int now[maxn];

int find(int idx) {
	if(fa[idx] == idx) {
		return idx;
	}
	return fa[idx] = find(fa[idx]);
}

node edge2[maxm];long long cnt2; 

signed main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int n; cin >> n;
	for(int i=1; i<=n+1; ++i) {
		fa[i] = i;
	}
	for(int i=1; i<=n; ++i) {
		cin >> x[i] >> y[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) {
		edge[++cnt] = {i, n+1, c[i], 0};
	}
	for(int i=1; i<=n; ++i) {
		for(int j=1; j<=n; ++j) {
			if(i>=j) continue;
			edge[++cnt] = {i, j, (k[i]+k[j]) * (abs(x[i]-x[j]) + abs(y[i]-y[j])), 1};
		}
	}
	sort(edge+1, edge+1+cnt);
	long long ans = 0, nowans=0;
	for(int i=1; i<=cnt; ++i) {
		int from = edge[i].from, to = edge[i].to;
		if(find(from) == find(to)) {
			continue;
		}
		ans += edge[i].w;
		if(edge[i].bl == 0) {
			now[edge[i].from] = 1;
			nowans ++;
		} else {
			edge2[++cnt2].from = from;
			edge2[cnt2].to = to;
		}
		int a = find(from), b = find(to);
		fa[a] = b;
	}
	cout << ans << endl;
	cout << nowans << endl;
	for(int i=1; i<=n; ++i) {
		if(now[i]) cout << i << " ";
	}
	cout << endl;
	cout << cnt2 << endl;
	for(int i=1; i<=cnt2; ++i) {
		cout << edge2[i].from << " " << edge2[i].to << endl;
	} 
	return 0; 
}
2024/8/4 00:37
加载中...