社区讨论

MnZn WA on 13 求调 || 祝好人RP++

CF1245DShichikuji and Power Grid参与者 6已保存回复 9

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
9 条
当前快照
1 份
快照标识符
@mhk7boy0
此快照首次捕获于
2025/11/04 14:42
4 个月前
此快照最后确认于
2025/11/04 14:42
4 个月前
查看原帖
CPP
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int n;
const int N=2010;
struct node{
	int x,y;
}p[N];
ll c[N],k[N];
ll cal(int x,int y,int x2,int y2){
	return abs(x-x2)+abs(y-y2);
}
const int M=4e6+10;
struct Node{
	int u,v;
	ll w;
}e[M];
bool cmp(Node a,Node b){
	return a.w<b.w;
}
int fa[N];
ll min_ans;
int num;
int power_station[N];
int nume;
int find(int x){
	if(x==fa[x])return x;
	return find(fa[x]);
}
int cnt;
struct NOde{
	int a,b;
}ans[M];
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>p[i].x>>p[i].y;
		fa[i]=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++){
		e[++cnt].u=0;
		e[cnt].v=i;
		e[cnt].w=c[i];
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(i==j)continue;
			ll w=(k[i]+k[j])*cal(p[i].x,p[i].y,p[j].x,p[j].y);
			e[++cnt].u=i;
			e[cnt].v=j;
			e[cnt].w=w;
		}
	}
	sort(e+1,e+cnt+1,cmp);
	for(int i=1;i<=cnt;i++){
//		cout<<nume<<" "<<num<<"\n";
		if(nume+num==n){
			break;
		}
		int from=e[i].u;
		int to=e[i].v;
		ll dis=e[i].w;
		int x=find(from);
		int y=find(to);
		if(x==y)continue;
		min_ans+=dis;
		if(from==0){
			num++;
			power_station[num]=to;
			continue;
		}
		nume++;
		fa[x]=y;
		ans[nume].a=from;
		ans[nume].b=to;
	}
	cout<<min_ans<<"\n";
	cout<<num<<"\n";
	for(int i=1;i<=num;i++){
		cout<<power_station[i]<<" ";
	} 
	cout<<"\n";
	cout<<nume<<"\n";
	for(int i=1;i<=nume;i++){
		cout<<ans[i].a<<" "<<ans[i].b<<"\n";
	}
	return 0;
}

回复

9 条回复,欢迎继续交流。

正在加载回复...