求救50pts
查看原帖
求救50pts
780301
Dying_zh楼主2023/12/27 21:53
#include<bits/stdc++.h>
using namespace std;
int n,k[2005],c[2005],x[2005],y[2005],cnt,fa[2005],ans,yj[2005],s,l;
bool vis[2005];
struct node{
	int u,v,w;
}edge[2005];
struct node2{
	int x,y;
}ege[2005];
bool cmp(node a,node b){
	return a.w<b.w;
}
void jz(int x,int y,int w){
	edge[++cnt]={x,y,w};
}
void init(){
	for(int i=1;i<=2*n;i++){
		fa[i]=i;
	}
}
int find(int x){
	if(fa[x]==x)return x;
	return fa[x]=find(fa[x]);
}
void hb(int x,int y){
	int xx=find(x),yy=find(y);
	if(xx==yy)return ;
	fa[xx]=yy;
}
void kr(){
	for(int i=1;i<=cnt;i++){
		int x1=find(edge[i].u);
		int y1=find(edge[i].v);
//		cout<<edge[i].u<<" "<<edge[i].v<<endl;
		if(x1==y1)continue;
		if(edge[i].u==0){
			yj[++s]=i;
			vis[i]=1;
		}
		else{
			if((vis[edge[i].u]||vis[edge[i].v])&&(!vis[edge[i].u]||!vis[edge[i].v])){
				ege[++l]={edge[i].u,edge[i].v};
				vis[edge[i].u]|=vis[edge[i].v];
			}
			
		}
		ans+=edge[i].w;
		hb(x1,y1);
	}
}
void print(){
	printf("%d\n",ans);
	printf("%d\n",s);
	for(int i=1;i<=s;i++)printf("%d ",yj[i]);
	printf("\n%d\n",l);
	for(int i=1;i<=l;i++)printf("%d %d\n",ege[i].x,ege[i].y);
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d%d",&x[i],&y[i]);
	}
	for(int i=1;i<=n;i++){
		scanf("%d",&c[i]);
		jz(0,i,c[i]);
	}
	for(int i=1;i<=n;i++){
		scanf("%d",&k[i]);
	}
	for(int i=1;i<n;i++){
		for(int j=i+1;j<=n;j++){
			int x1=abs(x[i]-x[j]),y1=abs(y[i]-y[j]);
			int w1=(x1+y1)*(k[i]+k[j]);
			jz(i,j,w1);
		}
	}
	sort(edge+1,edge+1+cnt,cmp);
	init();
	kr();
	print();
	return 0;
}
2023/12/27 21:53
加载中...