AcWing
3728. 城市通电
朴素prim算法，模板。prim算法的思想在于，将所有点分为两部分，一部分是已经visited的，另一部分是尚未visited的，每次从未访问的部分取出一个点(该点到已访问部分的距离最短)，将其标记为访问，并更新未访问点的距离。朴素prim算法的时间复杂度是$O(V^2+E)\sim O(V^2)$. prim算法也可以使用堆优化，优化后的时间复杂度为$O(ElogV)$.
此外，kruskal算法的时间复杂度为$O(ElogE)$. prim算法是选点加入，kruskal算法是选边加入。关于朴素prim/堆优化prim/kruskal，可以参考：图论——最小生成树：Prim算法及优化、Kruskal算法，及时间复杂度比较.
首先任意选出一个点，更新点到其他所有点之间的距离。此后n-1次遍历，每次遍历首先取出到已访问部分的距离最短点，将其标记为访问，遍历该点到其他未访问点的距离，如果比dist数组中的值更小，则更新。所维护的dist数组即为已访问部分到未访问的每一个点的最短距离。
对于本题，可以看作从虚拟源点(超级源点)到每个点之间有一条边，该边的权即为建立发电站所需要的大米。此外，除了虚拟源点之外的所有点之间都有边，权为布线所需的大米。这样，只要整个图是连通的，就能保证至少存在一个发电站。
使用fa数组记录生成树中每个节点的父节点。dist数组和visited数组是必需的。res/resw，resc，resk分别用来记录总需大米、建站点、布线点对。
#include <bits/stdc++.h>
using namespace std;
int n;
const int N = 2010;
typedef pair<int, int> PII;
PII loc[N];
long long wc[N], wk[N];
vector<int> resc;
vector<PII> resk;
int dist[N], fa[N];
bool visited[N];
long long getmoney(int a, int b){
int x1 = loc[a].first, y1 = loc[a].second;
int x2 = loc[b].first, y2 = loc[b].second;
int len = abs(x1 - x2) + abs(y1 - y2);
return (long long)(wk[a] + wk[b]) * len;
}
long long prim(){
memset(dist, 0x3f, sizeof dist);
memset(visited, false, sizeof visited);
dist[0] = 0;
visited[0] = 1;
for(int i = 1; i <= n; i++) dist[i] = wc[i];
long long res = 0;
for(int i = 1; i <= n; i++){
int minele = -1;
for(int j = 1; j <= n; j++) if(!visited[j] && (minele == -1 || dist[j] < dist[minele])){
minele = j;
}
visited[minele] = 1;
res += dist[minele];
if(fa[minele] == 0) resc.push_back(minele);
else resk.push_back({fa[minele], minele});
for(int j = 1; j <= n; j++) if(!visited[j] && dist[j] > getmoney(minele, j)){
dist[j] = getmoney(minele, j);
fa[j] = minele;
}
}
return res;
}
int main(){
cin >> n;
for(int i = 1; i <= n; i++){
int x, y;
cin >> x >> y;
loc[i].first = x, loc[i].second = y;
}
for(int i = 1; i <= n; i++) cin >> wc[i];
for(int i = 1; i <= n; i++) cin >> wk[i];
long long resw = prim();
cout << resw << endl;
cout << (int)resc.size() << endl;
for(int i = 0; i <= (int)resc.size() - 1; i++) cout << resc[i] << " \n"[i == (int)resc.size() - 1];
cout << (int)resk.size() << endl;
for(int i = 0; i <= (int)resk.size() - 1; i++) cout << resk[i].first << ' ' << resk[i].second << endl;
return 0;
}