File size: 1,559 Bytes
1fd0050 | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 | #include <bits/stdc++.h>
using namespace std;
struct DSU {
int n;
vector<int> p, r;
DSU(int n=0): n(n), p(n+1), r(n+1,0) { iota(p.begin(), p.end(), 0); }
int find(int x){ return p[x]==x?x:p[x]=find(p[x]); }
bool unite(int a,int b){
a=find(a); b=find(b);
if(a==b) return false;
if(r[a]<r[b]) swap(a,b);
p[b]=a;
if(r[a]==r[b]) r[a]++;
return true;
}
};
struct Edge {
int u, v;
long long w;
bool operator<(Edge const& other) const {
if (w != other.w) return w < other.w;
if (u != other.u) return u < other.u;
return v < other.v;
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
if(!(cin >> T)) return 0;
while(T--){
int n;
if(!(cin >> n)) return 0;
vector<Edge> edges;
edges.reserve(1LL * n * (n - 1) / 2);
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
long long d;
cin >> d;
if (j < i) {
edges.push_back({i+1, j+1, d});
}
}
}
sort(edges.begin(), edges.end());
DSU dsu(n);
int cnt = 0;
for (auto &e : edges) {
if (dsu.unite(e.u, e.v)) {
cout << e.u << ' ' << e.v << ' ' << e.w << '\n';
if (++cnt == n - 1) break;
}
}
// If multiple test cases, separate outputs by nothing as per typical batch processing
}
return 0;
} |