Codeforces Round #597 (Div. 2) D. Shichikuji and Power Grid

链接：https://codeforces.com/problemset/problem/1245/D

题意：n个城市，选择一些城市建造电厂，选择一些城市和电厂城市连接或通过连接其他城市间接和电厂城市连接，建造电厂的花费为c，连接两城市的花费为两城市的k值和乘上曼哈顿距离，问最小花费及哪些城市建造电厂，连接哪些城市

思路：求最小生成森林，可以引入超级源点，将超级源点与所有点连接，边权为c值，然后求mst，最后mst边权和即为最小花费，与超级源点连接的点为电厂城市

代码：

  1 #include<bits/stdc++.h>
  2 #define inf 0x3f3f3f3f
  3 #define ms(a) memset(a,0,sizeof(a))
  4 #define pii pair<int,int>
  5 using namespace std;
  6 typedef long long ll;
  7 
  8 const int M = int(1e5) + 5;
  9 const int mod = int(1e9) + 7;
 10 
 11 int n;
 12 
 13 int fa[M];
 14 void init(){
 15     for(int i=0;i<M;i++){
 16         fa[i]=i;
 17     }
 18 }
 19 int find(int x){
 20     return fa[x]==x?x:fa[x]=find(fa[x]);
 21 }
 22 int merge(int x,int y){
 23     int xx=find(x);
 24     int yy=find(y);
 25     fa[xx]=yy;
 26 }
 27 
 28 struct node{
 29     int x,y;
 30 }a[2010];
 31 int c[2010],k[2010];
 32 
 33 struct nod{
 34     int from,to;
 35     ll cost;
 36 };
 37 vector<nod> edge;
 38 bool cmp(nod a,nod b){
 39     return a.cost<b.cost;
 40 }
 41 int tot;
 42 
 43 vector<nod> mst;
 44 ll mon;
 45 void kruskal(){
 46     sort(edge.begin(),edge.end(),cmp);
 47     for(int i=0;i<edge.size();i++){
 48         if(find(edge[i].from) != find(edge[i].to)){
 49             mst.push_back(edge[i]);
 50             merge(edge[i].from,edge[i].to);
 51             mon += edge[i].cost;
 52         }
 53     }
 54 }
 55 
 56 set<int> s;
 57 priority_queue<pii,vector<pii>,greater<pii> > pq;
 58 
 59 int main(){
 60     init();
 61 
 62     cin >> n;
 63     for(int i=1;i<=n;i++){
 64         cin >> a[i].x >> a[i].y; 
 65     }
 66     for(int i=1;i<=n;i++){
 67         cin >> c[i]; 
 68     }
 69     for(int i=1;i<=n;i++){
 70         cin >> k[i]; 
 71     }
 72 
 73     for(int i=1;i<=n;i++){
 74         nod tem;
 75         tem.from=0;tem.to=i;
 76         tem.cost=c[i];
 77         edge.push_back(tem);
 78     }
 79 
 80     for(int i=1;i<=n;i++){
 81         for(int j=i+1;j<=n;j++){
 82             int dis=abs(a[i].x-a[j].x)+abs(a[i].y-a[j].y);
 83             int per=k[i]+k[j];
 84             edge.push_back({i,j,1LL*dis*per});
 85         }
 86     }
 87 
 88     kruskal();
 89 
 90     cout << mon << endl;
 91 
 92     for(int i=0;i<mst.size();i++){
 93         if(mst[i].from==0){
 94             s.insert(mst[i].to);
 95         }
 96         else{
 97             pq.push({mst[i].from,mst[i].to});
 98         }
 99     }
100     cout << s.size() << endl;
101     for(set<int>::iterator it=s.begin();it!=s.end();it++){
102         cout << *it << " ";
103     }
104     cout << endl;
105 
106     cout << pq.size() << endl;
107     while(!pq.empty()){
108         cout << pq.top().first << " " << pq.top().second << endl;
109         pq.pop();
110     }
111     return 0;
112 }