简单讲解一下题意：在一个二维坐标上有n个城市(坐标表示)，每个城市可以选择自己供电花费b[i]，也可以选择来自其他城市的电花费c，求最小花销，每一个供电的城市序号以及连接路径！ 赛时 脑子：我会了，快写，赶紧的！ 手：不，你还不会，需要冷静。。。 一个比较好的思路：我们可以构建一个虚点0，每一个直接与0相连的城市都是自己供电的，其他的都是通过连接来得到电。 克鲁斯卡尔算法注意合并两个点的时候指向城市自己发电小的那一个城市，从而保证最后一定都指向0；
#include<stdio.h> #include<algorithm> #include<string.h> using namespace std; typedef long long ll; const int N = 3e3+5; const int mod = 1e9+7; struct ab{ int x,y; }a[N]; int b[N],c[N]; struct edge{ int to,from; ll w; bool operator < (const edge& x) const{ return w<x.w; } }ma[N*N]; int fa[N],x1[N],y1[N],z1[N]; ll sum[N]; int get(int x) { if(fa[x]==x) return x; else return fa[x]=get(fa[x]); } int main() { int n; scanf("%d",&n); int i,j,k; int cnt=0,cnt1=0,cnt2=0; for(i=1;i<=n;i++) scanf("%d %d",&a[i].x,&a[i].y); for(i=1;i<=n;i++) scanf("%d",&b[i]); for(i=1;i<=n;i++) scanf("%d",&c[i]); for(i=1;i<=n;i++) ma[++cnt] =(edge) {0,i,b[i]}; for(i=0;i<=n;i++) fa[i]=i,sum[i]=0; b[0]=0; for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { int p=a[i].x-a[j].x,q=a[i].y-a[j].y; if(p<0) p=-p; if(q<0) q=-q; ma[++cnt].w=1ll*(p+q)*(c[i]+c[j]),ma[cnt].from=i,ma[cnt].to=j; } } sort(ma,ma+1+cnt); ll ans=0,ans1=1; for(i=1;i<=cnt;i++) { int u=ma[i].to,v=ma[i].from; int g=get(v); if(u==0&&g!=0) { ans+=b[v]; z1[++cnt2]=v; fa[g]=0; continue; } int p=get(u),q=get(v); if(p!=q) { ans+=ma[i].w; x1[++cnt1]=u,y1[cnt1]=v; if(b[p]>b[q]) { fa[p]=q; } else fa[q]=p; } } printf("%lld\n%d\n",ans,cnt2); for(i=1;i<=cnt2;i++) printf("%d\n",z1[i]); printf("%d\n",cnt1); for(i=1;i<=cnt1;i++) { printf("%d %d\n",x1[i],y1[i]); } }