D.Shichikuji and Power Grid（思维
Codeforces Round #597 (Div. 2)
题意：n个城市，每个城市要么自己建发电站（花费Ci），要么和建有发电站的城市相连（花费Ki+Kj），问所有城市通电的最小花费，并输出方案
比赛的时候根本没写到这里，昨晚真的。。。毒瘤场，队友对着A过的代码改了半小时，我快读板子出锅了Debug好久才D出来。。
题目如果只有第二种建造方法，不就是最小生成树板子吗？？？（设定一个建造发电厂）
再仔细一想，第一种情况的建造我们也可以把他改成两个点之间的联系：
设定一个源点0，并将源点的Ki值设定为0，那么第一种情况就是i点与0点建边了！
#include <bits/stdc++.h>
using namespace std;
#define endll '\n'
#define C getchar()
using ll = long long;
#define pi acos(-1.0)
#define INF 0x3f3f3f3f
#define mod 1000000007
#define pii pair<int, int>
const int MAXN = 1e6 + 10;
#define stop system("pause")
#define lowbit(x) ((x) & (-x))
#define Temp template <typename T>
#define mem(a, b) memset(a, b, sizeof(a))
#define rep(i, a, b) for (int i = a; i <= b; ++i)
Temp inline void rd(T &s)
{
s = 0;T t = 1, k = C;
for (; k < '0' || k > '9'; k = C)if (k == '-') t = -1;
for (; k >= '0' && k <= '9'; k = C) s = (s << 1) + (s << 3) + (k ^ 48);
s *= t;
}
const int N = 2005;
int x[N], y[N], k[N],c[N],par[N];
ll cost[N][N],dist[N];
bool done[N];
int main()
{
int n;rd(n);
rep(i,1,n) rd(x[i]),rd(y[i]);
rep(i,1,n) rd(c[i]);
rep(i,1,n) rd(k[i]);
rep(i,1,n) rep(j,1,n) cost[i][j] = 1LL * (k[i] + k[j]) * (abs(x[i] - x[j]) + abs(y[i] - y[j]));
for (int i = 1; i <= n; i++) cost[0][i] = c[i];//秒啊%%%
for (int i = 1; i <= n; i++) dist[i] = 1e18;
vector<int> ps;
vector<pii > edges;
mem(par, -1);
ll ans = 0;
rep(i,0,n)
{
ll mn = 1e18, id = -1;
rep(i,0,n)
if (!done[i] && dist[i] < mn)
mn = dist[i],id = i;
done[id] = 1;
ans += dist[id];
if (par[id] == 0)
ps.push_back(id);
else if (par[id] > 0)
edges.push_back({par[id], id});
rep(i,0,n)
if (dist[i] > cost[id][i])
dist[i] = cost[id][i],par[i] = id;
}
cout << ans << endl<< ps.size() << endl;
for (int x : ps) cout << x << " ";
cout << endl<< edges.size() << endl;
for (auto pr : edges) cout << pr.first << " " << pr.second << "\n";
} 
查看4道真题和解析