求助 WA on #4,已开 long long
查看原帖
求助 WA on #4,已开 long long
690315
array2022楼主2024/7/23 16:05
#include<bits/stdc++.h>
#define ll long long
using namespace std;
struct edge{
	int f,t;
	ll wei;
}e[4002005],e2[2005];
bool cmp(edge a,edge b){
	return a.wei<b.wei;
}
ll n,x[2005],y[2005],k[2005],c[2005],fa[2005],w[2005],cnt,f,ans,v,m;
int find(int a){
	if (fa[a]==a) return a;
	return fa[a]=find(fa[a]);
}
void join(int a,int b){
	fa[find(a)]=find(b);
}
int main(){
	ios::sync_with_stdio(false);
	cin>>n;
	for (int i=1;i<=n;i++){
		cin>>x[i]>>y[i];
	}
	for (int i=1;i<=n;i++){
		cin>>c[i];
		e[++cnt].t=i; e[cnt].wei=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++){
			e[++cnt].wei=(k[i]+k[j])*(abs(x[i]-x[j])+abs(y[i]-y[j]));
			e[cnt].f=i; e[cnt].t=j;
		}
	}
	sort(e+1,e+cnt+1,cmp);
	for (int i=0;i<=cnt;i++){
		fa[i]=i;
	}
	for (int i=1;i<=cnt&&f<=n;i++){
		if (find(e[i].f)!=find(e[i].t)){
			join(e[i].f,e[i].t);
			ans+=e[i].wei; f++;
			if (e[i].f==0){
				w[++v]=e[i].t;
			}
			else{
				e2[++m].f=min(e[i].f,e[i].t); e2[m].t=max(e[i].t,e[i].f);
			}
		}
	}
	sort(w+1,w+1+v);
	cout<<ans<<"\n"<<v<<"\n";
	for (int i=1;i<=v;i++){
		cout<<w[i]<<" ";
	}
	cout<<"\n"<<m<<"\n"; 
	for (int i=1;i<=m;i++){
		cout<<e2[i].f<<" "<<e2[i].t<<"\n";
	}
	return 0;
}
2024/7/23 16:05
加载中...