求调 #4 WA
查看原帖
求调 #4 WA
450845
RTDyjt楼主2023/7/28 15:33
#include <bits/stdc++.h>
using namespace std;
const int N = 2e3+10;
typedef long long LL;
typedef pair <int,int> PII;
struct node {
	int u,v;
	LL len;
};
int n;
int x[N],y[N];
LL c[N],k[N];
int f[N];
vector <node> g;
void add(int a,int b,int c){
	g.push_back({a,b,c});
}
LL get(int i,int j){
	return (k[i]+k[j])*(abs(x[i]-x[j])+abs(y[i]-y[j]));
}
bool cmp(node a,node b){
	return a.len < b.len;
}
int find(int x){
	if(x == f[x])	return x;
	return f[x] = find(f[x]);
}
vector <int> build;
vector <PII> line;
LL kruskal(){
	sort(g.begin(),g.end(),cmp);
	LL ans = 0;
	int cnt = 0,idx = 0;
	while(cnt < n){
		int u = g[idx].u,v = g[idx].v,len = g[idx].len;
		int fu = find(u),fv = find(v);
		if(fu != fv){
			cnt++;
			ans += len;
			f[fu] = fv; 
			if(u == n+1 || v == n+1){
				build.push_back(min(u,v));
			}else{
				line.push_back({u,v});
			}
		}
		idx++;
	}
	return ans;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	cin >> n;
	for(int i = 1;i <= n;i++){
		f[i] = i;
		cin >> x[i] >> y[i];
	}
	f[n+1] = n+1;
	for(int i = 1;i <= n;i++){
		cin >> c[i];
		add(n+1,i,c[i]);
	}
	for(int i = 1;i <= n;i++){
		cin >> k[i];
	}
	for(int i = 1;i <= n;i++){
		for(int j = i+1;j <= n;j++){
			add(i,j,get(i,j));
		}
	}
	cout << kruskal() << endl;
	cout << build.size() << endl;
	for(int i = 0;i < build.size();i++){
		cout <<build[i] << " ";
	}
	cout << endl << line.size() <<endl;
	for(int i = 0;i < line.size();i++){
		cout << line[i].first << " " << line[i].second << endl;
	}
	

	return 0;
}

#4 WA,样例都过,开long long了,用的vector存图

2023/7/28 15:33
加载中...