Codeforces

Luogu

分析

新建一个点 $0$ 表示建电站。

从 $0$ 向每个点 $i$ 连边权为 $c_i$ 的边；$i,j\;(i>0,j>0)$ 之间连边权为 $\operatorname{dis}(i,j)\times(k_i+k_j)$ 的边。

那么最小生成树即为答案。正确性显然。

输出方案根据最小生成树上的边搞一搞就好了。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#define re register
using namespace std;
typedef long long ll;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=2000+10;

int n,x[N],y[N],c[N],k[N];
ll ans; vector<int> op;

inline int dis(int i,int j) {
    return abs(x[i]-x[j])+abs(y[i]-y[j]);
}

int f[N];
inline int find(int x) { return x==f[x]?x:f[x]=find(f[x]); }

int cnt=0;
struct edge { int u,v; ll w; } e[N*N];
bool operator <(edge a,edge b) { return a.w<b.w; }

int main() {
    n=read();
    for (re int i=1;i<=n;++i) x[i]=read(),y[i]=read();
    for (re int i=1;i<=n;++i) c[i]=read();
    for (re int i=1;i<=n;++i) k[i]=read();
    for (re int i=1;i<=n;++i) {
        e[++cnt]=(edge){0,i,c[i]};
        for (re int j=i+1;j<=n;++j)
            e[++cnt]=(edge){i,j,1ll*(k[i]+k[j])*dis(i,j)};
    }
    for (re int i=0;i<=n;++i) f[i]=i;
    sort(e+1,e+cnt+1);
    for (re int i=1;i<=cnt;++i) {
        int p=find(e[i].u),q=find(e[i].v);
        if (p!=q) ans+=e[i].w,op.push_back(i),f[p]=q;
    }
    printf("%lld\n",ans);
    int cnt1=0,cnt2=0;
    for (re int i:op) {
        if (!e[i].u||!e[i].v) ++cnt1;
        else ++cnt2;
    }
    printf("%d\n",cnt1);
    for (re int i:op)
        if (!e[i].u||!e[i].v) printf("%d ",e[i].u+e[i].v);
    puts("");
    printf("%d\n",cnt2);
    for (re int i:op)
        if (e[i].u&&e[i].v) printf("%d %d\n",e[i].u,e[i].v);
    return 0;
}