感觉没啥人写堆优化Prim,这里补充一个。
C++ 代码
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int N = 110;
const int M = 500;
int h[N], e[M], ne[M], w[M], idx;
int n, k;
int dist[N];
bool st[N];
int prim(int src){
dist[src] = 0;
int mst = 0;
priority_queue<PII, vector<PII>, greater<PII>> pq;
pq.push({0,src});
while(!pq.empty()){
PII curr = pq.top();
pq.pop();
int curr_node = curr.second;
if(st[curr_node]) continue;
st[curr_node] = true;
mst += curr.first;
for(int i = h[curr_node]; i != -1; i = ne[i]){
int node = e[i];
if(dist[node] > w[i]){
dist[node] = w[i];
pq.push({dist[node], node});
}
}
}
return mst;
}
void add(int a, int b, int c){
e[idx] = b;
ne[idx] = h[a];
w[idx] = c;
h[a] = idx ++;
}
int main(){
cin >> n >> k;
memset(h, -1, sizeof h);
memset(dist, 0x3f3f3f, sizeof dist);
int total = 0;
while(k --){
int a, b, c;
cin >> a >> b >> c;
add(a, b, c);
add(b, a, c);
total += c;
}
for(int i = 1; i <= n; i ++){
if(!st[i]) total -= prim(i);
}
cout << total << endl;
return 0;
}
老哥。朴素版报错了,过不了,就是错误。。