两个模板：
kruskal
#include<stdio.h>
#include<queue>
#include<algorithm>
#include<iostream>
using namespace std;
const int maxn = ;
int f[maxn];
int find(int x) {
if (f[x] == x)return x;
else return(f[x] = find(f[x]));
}
bool same(int x, int y) {
return (find(x) == find(y));
}
void un(int x, int y) {
int u = find(x);
int v = find(y);
if (u == v)return;
f[u] = v;
}
struct edge {
int from, to;
long long w;
}e[maxn];
bool cmp(edge a, edge b) {
return a.w < b.w;
}
int main() {
int n, m;
while (cin >> m >> n) {
if (m == )break;
for (int i = ; i < m; i++) {
//int x, y, z;
cin >> e[i].from >> e[i].to >> e[i].w;
}
for (int i = ; i <= n; i++)f[i] = i;
sort(e, e + m, cmp);
int res = ;
for (int i = ; i < m; i++) {
if (same(e[i].from, e[i].to)) continue;
res += e[i].w;
un(e[i].from, e[i].to);
}
for (int i = ; i <= n; i++) {
if (!same(i, ))res = -;
}
if (res == -)cout << '?' << endl;
else cout << res<<endl;
}
}
prim
#include<stdio.h>
#include<queue>
#include<algorithm>
#include<iostream>
#include<vector>
using namespace std;
const int maxn = ;
struct edge {
int to;
long long w;
edge(int to = , long long w = ) :to(to), w(w) {}
bool operator<(const edge &a)const {
return w > a.w;
}
};
vector<edge> E[maxn];
bool vis[maxn];
priority_queue<edge> Q; long long prim() {
long long ret = ;
vis[] = ;
int sz = E[].size(); for (int i = ; i < sz; i++) Q.push(E[][i]);
while (!Q.empty()) {
edge t = Q.top(); Q.pop();
if (vis[t.to])continue;
ret += t.w; vis[t.to] = ;
int sz = E[t.to].size(); for (int i = ; i < sz; i++) Q.push(E[t.to][i]);
}
return ret;
} int main() {
int m, n;
while (cin >> m >> n) {
if (m == )break;
for (int i = ; i <= n; i++)E[i].clear(),vis[i]=;
while (!Q.empty()) Q.pop();
for (int i = ; i < m; i++) {
int a, b, c;
cin >> a >> b >> c;
E[a].push_back(edge(b, c));
E[b].push_back(edge(a, c));
}
int res = prim();
for (int i = ; i <= n; i++) if (!vis[i]) res = -;
if (res == -)cout << '?' << endl;
else cout << res << endl; }
}