社区讨论
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 条回复,欢迎继续交流。
正在加载回复...