[C++] 純文本查看 復制代碼
#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
#define MAX 106
using namespace std;
int parentof[MAX];
int groupn;
int N, M, T;
void init(){
for(int i = 0; i < MAX; ++i) parentof = i;
}
int root(int a){
if (parentof[a] == a) return a;
return parentof[a] = root(parentof[a]);
}
void join(int a, int b){
//printf(": %d %d\n", a, b);
a = root(a);
b = root(b);
parentof = a;
}
struct edge {
int u;
int v;
int w;
};
vector<edge> data;
vector<int> D;
bool cmp(edge a, edge b){
return a.w < b.w;
}
int MST(){
init();
groupn = N - 1;
int SUM = 0;
for(int i = 0; i < data.size(); ++i){
if(root(data.u) != root(data.v)){
SUM += data.w;
D.push_back(i);
join(data.u, data.v);
groupn--;
}
}
//cout << D.size() << endl;
return SUM;
}
int MST2(int disregard){
init();
groupn = N - 1;
int SUM = 0;
for(int i = 0; i < data.size(); ++i){
if(D[disregard] == i) continue;
if(root(data.u) != root(data.v)){
SUM += data.w;
join(data.u, data.v);
groupn--;
}
}
return SUM;
}
int main(){
scanf("%d", &T);
while(T--){
scanf("%d %d", &N, &M);
data.clear();
D.clear();
edge tmp;
for(int i = 0; i < M; ++i){
data.push_back(tmp);
scanf("%d %d %d", &data.u, &data.v, &data.w);
}
sort(data.begin(), data.end(), cmp);
int m1 = MST();
int m2 = INT_MAX;
//cout << D.size() << endl;
for(int k = 0; k < D.size(); ++k){
//cout << k << endl;
m2 = min(m2, MST2(k));
}
printf("%d %d\n", m1, m2);
}
return 0;
}