D. Shichikuji and Power Grid
题意
给定 n 个点，在某个点上建立一个基站要花费ci，连接两点要花费(|xi−xj|+|yi−yj|)∗(ki+kj)。
对于一个点要么建立基站，要么连接建立基站的点。问最小代价是多少，同时输出建立基站的点和线路。
题解
建立一个超级根，对于每个城市建立发电站，连接一条权值为ci的边再把每个城市之间连接电线的花费算出来
跑最小生成树 kruskal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
| # include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2005;
ll x[maxn],y[maxn],cont=0;
ll costA[maxn],costB[maxn];
vector<int> station,connect[maxn];
struct Node{
ll st,to;
ll val;
}G[maxn*maxn];
int root[maxn];
inline int found(int x){
if(root[x]!=x)root[x]=found(root[x]);
return root[x];
}
ll kruskal(int cnt){
ll sum=0;
for(int i=0;i<30;i++)root[i]=i;
for(int i=0;i<cnt;i++){
int u=G[i].st;
int v=G[i].to;
if(found(u)!=found(v)){
root[found(u)]=root[found(v)];
sum+=G[i].val;
if(G[i].st==0)station.push_back(G[i].to);
else connect[G[i].st].push_back(G[i].to),cont++;
}
}
return sum;
}
bool cmp(Node a,Node b){return a.val<b.val;}
int main(){
int n,cnt=0;cin>>n;
for(int i=0;i<=n;i++)root[i]=i;
for(int i=1;i<=n;i++)cin>>x[i]>>y[i];
for(int i=1;i<=n;i++){
cin>>costA[i];
G[cnt].st=0;
G[cnt].to=i;
G[cnt].val=costA[i];
cnt++;
}
for(int i=1;i<=n;i++)cin>>costB[i];
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(i==j)continue;
G[cnt].st=i;
G[cnt].to=j;
G[cnt].val=(abs(x[i]-x[j])+abs(y[i]-y[j]))*(costB[i]+costB[j]);
cnt++;
}
}
sort(G,G+cnt,cmp);
ll ans=kruskal(cnt);
cout<<ans<<endl;
cout<<station.size()<<endl;
int lenth=station.size();
for(int i=0;i<lenth;i++)cout<<station[i]<<" ";
cout<<endl<<cont<<endl;
for(int i=1;i<=n;i++){
if(connect[i].empty())continue;
else {
int len=connect[i].size();
for(int j=0;j<len;j++){
cout<<i<<" "<<connect[i][j]<<endl;
}
}
}
}
|