传送门 题意： 在矩阵上给n个点，点与点之间的距离为他们的曼哈顿距离。 现在可以建立若干个发电站在这n个点上，也可以在若干对点上建立边，使得每一个连通子图都至少有一个发电站。 每一个点都有两种权值，建边权值ki和建发电站权值ci，如果i、j之间要建立边，那么边权为其曼哈顿距离*（ki+kj）;
思路： 初始想法，是跑一个最小生成树，然后进行建站割边。 答案思路， 构建一个额外的点 s ，s到每个点的边权为这个点建发电站的权值，即ci; 这样就能将点权转化为边权，跑一遍最小生成树即可。
由于最后的电网是一棵树，那我们把 额外点 s 删掉后，会分割为若干个连通子树，而s与每一个子树的连边，即为在这颗子树上建发电站的最小花费（最小的ci）。
AC代码
#include<cstdio> #include<cctype> #include<vector> #include<algorithm> #include<cstring> using namespace std; typedef long long LL; typedef pair<int,int> pii; typedef pair<LL,LL> pLL; const int N=2e3+5; const int inf=0x3f3f3f3f; const LL mod=1e9+7; #define ls (i<<1) #define rs (i<<1|1) #define fi first #define se second #define mk make_pair #define mem(a,b) memset(a,b,sizeof(a)) LL read() { LL x=0,t=1; char ch; while(!isdigit(ch=getchar())) if(ch=='-') t=-1; while(isdigit(ch)){ x=10*x+ch-'0'; ch=getchar(); } return x*t; } LL f[N],n; pLL a[N]; vector<LL> to; vector<pLL> uv; LL c[N],k[N]; struct edge { LL u,v,w; edge(){} edge(LL uu,LL vv,LL ww) { u=uu; v=vv; w=ww; } friend bool operator < (edge p,edge q) { return p.w<q.w; } }e[N*N]; inline void init() { for(int i=0;i<=n;i++) f[i]=i; } int getf(int r) { int i=r,j=f[r]; while(r!=f[r]) r=f[r]; while(i!=r) { f[i]=r; i=j; j=f[i]; } return r; } int main() { n=read(); init(); for(int i=1;i<=n;i++) { a[i].fi=read(); a[i].se=read(); } for(int i=1;i<=n;i++) c[i]=read(); for(int i=1;i<=n;i++) k[i]=read(); int tot=0; for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) { e[++tot]=edge(i,j,(k[i]+k[j])*(abs(a[i].fi-a[j].fi)+abs(a[i].se-a[j].se) ) ); e[++tot]=edge(j,i,(k[i]+k[j])*(abs(a[i].fi-a[j].fi)+abs(a[i].se-a[j].se) ) ); } for(int i=1;i<=n;i++) { e[++tot]=edge(i,0,c[i]); e[++tot]=edge(0,i,c[i]); } sort(e+1,e+tot+1); LL ans=0; for(int i=1;i<=tot;i++) { edge tmp=e[i]; int fx=getf(tmp.u),fy=getf(tmp.v); if(fx==fy) continue; f[fy]=fx; ans+=tmp.w; if(!tmp.u) to.push_back(tmp.v); else if(!tmp.v) to.push_back(tmp.u); else uv.push_back(mk(tmp.u,tmp.v)); } printf("%lld\n",ans); printf("%d\n",to.size()); sort(to.begin(),to.end()); for(int i=0;i<to.size();i++) printf("%lld%c",to[i],i==to.size()-1?'\n':' '); printf("%d\n",uv.size()); sort(uv.begin(),uv.end()); for(int i=0;i<uv.size();i++) printf("%lld %lld\n",uv[i].fi,uv[i].se); return 0; }