https://codeforces.com/contest/1245/problem/D 题意 ： 给了你一堆城市 让你给他们建发电站 or 把他们连到有点的城市 我们道路的花费会是 题目中给的 ( k [ v ] + k [ u ] ) ∗ ( ( u , v ) 曼 哈 顿 距 离 ) (k[v] + k[u]) * ((u, v)曼哈顿距离) (k[v]+k[u])∗((u,v)曼哈顿距离) 直接建立发电站花费是 c[i] 现在 让你求 全部城市有电的最小花费(默认初始都没有电)
思路： 我们考虑建立一个虚电与其他所有的城市相连 他们的边权 就是这个城市建立发电站的花费 其他的 城市我们正常 n 2 n^2 n2 边权就是道路花费 暴力建图 这 既能保证图联通供电 也 简化的模型 仅仅只跑一次 kruskal
#include <bits/stdc++.h> using namespace std; const int maxn = 2e6 + 2005; const int mod = 1e9 + 7; int n; pair<int, int> p[2005]; int k[2005], c[2005]; struct Edge { int u, v; long long dis; } e[maxn]; int cnt; int pre[2005]; void init() {for(int i = 0; i <= n; i ++) pre[i] = i;} int finds(int x) {return x == pre[x] ? x : pre[x] = finds(pre[x]);} long long recost(int u, int v) { return (1ll * k[u] + k[v]) * (1ll * abs(1ll * p[u].first - p[v].first) + abs(p[u].second - p[v].second)); } void ade(int u, int v) { e[++ cnt] = Edge{u, v, recost(u, v)}; } vector<pair<int, int> > path; vector<int> powers; long long kruskal() { long long ans = 0; init(); sort(e + 1, e + 1 + cnt, [](const Edge & a, const Edge & b) { return a.dis < b.dis; }); for(int i = 1; i <= cnt; i ++) { int fu = finds(e[i].u), fv = finds(e[i].v); if(fu != fv) { pre[fu] = fv; ans += e[i].dis; if(e[i].v == n) powers.push_back(e[i].u); else path.push_back(make_pair(e[i].u, e[i].v)); } } return ans; } signed main() { cin >> n; for(int i = 1; i <= n; i ++) cin >> p[i].first >> p[i].second; for(int i = 1; i <= n; i ++) cin >> c[i]; for(int i = 1; i <= n; i ++) cin >> k[i]; for(int i = 1; i <= n; i ++) for(int j = i + 1; j <= n; j ++) ade(i, j); n ++; for(int i = 1; i < n; i ++) e[++ cnt] = Edge{i, n, c[i]}; cout << kruskal() << endl; cout << powers.size() << endl; for(int i = 0; i < powers.size(); i ++) { if(i != 0) cout << " "; cout << powers[i] ; if(i == powers.size() - 1) cout << endl; } cout << path.size() << endl; for(int i = 0; i < path.size(); i ++) cout << path[i].first << " " << path[i].second << endl; return 0; }