每个城市可以选择自己建发电站或者连边到其他城市以得到供电，问最小代价。
考场上想了几个贪心做法，但是最后都被自己yy卡掉了，正解简单但是并不显然，就是新建一个节点0，连边到这个节点表示在这个城市建发电站，城市间的连边就是真实的电线，然后跑最小生成树就是对的，因为跑出来的方案代价就是最小代价，而且方案也很好确定。
#include<bits/stdc++.h> using namespace std; const int N=2010; int n; struct edge{ int x,y; long long c; bool operator<(const edge q)const{ return c<q.c; } }s[N*N]; struct node{ int x,y; }p[N]; int fa[N],mmin[N],c[N],op; bool tf[N]; long long ans=0; int findpa(int x){ if(fa[x]!=x) return fa[x]=findpa(fa[x]); return x; } int main(){ scanf("%d",&n); int x,t; for(int i=1;i<=n;i++) scanf("%d %d",&p[i].x,&p[i].y); for(int i=1;i<=n;i++) scanf("%d",&x),s[++t]=(edge){0,i,x},fa[i]=i; for(int i=1;i<=n;i++) scanf("%d",&c[i]); for(int i=1;i<=n;i++){ int y; long long mminc=1e18; for(int j=i+1;j<=n;j++) if(j!=i) s[++t]=(edge){i,j,1ll*(abs(p[i].x-p[j].x)+abs(p[i].y-p[j].y))*(c[i]+c[j])}; } sort(s+1,s+1+t); for(int i=1;i<=t;i++){ int fx=findpa(s[i].x),fy=findpa(s[i].y); if(fx!=fy){ if(s[i].x==0) tf[s[i].y]=true,op++; fa[fy]=fx,ans+=s[i].c,s[i].c=1; } else s[i].c=0; } printf("%I64d\n",ans); printf("%d\n",op); for(int i=1;i<=n;i++) if(tf[i]) printf("%d ",i);printf("\n"); printf("%d\n",n-op); for(int i=1;i<=t;i++) if(s[i].c && s[i].x) printf("%d %d\n",s[i].x,s[i].y); }
