题目：http://acm.jlu.edu.cn/joj/showproblem.php?pid=1170
根据题目的输入特点，用kruskal算法最方便。
代码：
- #include <cstdio>
- #include <vector>
- #include <algorithm>
- using namespace std;
- struct Edge {
- int from, to, length;
- Edge(int f, int t, int l):from(f),to(t),length(l){}
- Edge() {}
- Edge(const Edge& e) {
- from = e.from;
- to = e.to;
- length = e.length;
- }
- bool operator<(const Edge& e) const {
- return length < e.length;
- }
- };
- int n;
- int main() {
- freopen("in.txt", "r", stdin);
- int m;
- int ans;
- int id[32];
- scanf("%d", &m);
- while(m--) {
- int a,b,c;
- vector<Edge> ve;
- scanf("%d", &n);
- while(scanf("%d%d%d", &a, &b, &c), a||b||c) {
- ve.push_back(Edge(a,b,c));
- }
- ans = 0;
- for(int i = 0; i <= n; i++)
- id[i] = i;
- sort(ve.begin(), ve.end());
- const int s = ve.size();
- for(int i = 0;i < s; i++) {
- int from = ve[i].from, to = ve[i].to;
- if(id[from] != id[to]) {
- replace(id, id+n+1, (int)id[to], (int)id[from]);
- ans += ve[i].length;
- }
- }
- printf("%d/n", ans);
- }
- return 0;
- }