这道题目麻烦在输出的时候需要按照字典序输出,不过写了 Compare 函数还是比较简单的
因为是裸的 Kruscal ,所以就直接上代码了~
Source Code :
//#pragma comment(linker, "/STACK:16777216") //for c++ Compiler
#include <stdio.h>
#include <iostream>
#include <fstream>
#include <cstring>
#include <cmath>
#include <stack>
#include <string>
#include <map>
#include <set>
#include <list>
#include <queue>
#include <vector>
#include <algorithm>
#define Max(a,b) (((a) > (b)) ? (a) : (b))
#define Min(a,b) (((a) < (b)) ? (a) : (b))
#define Abs(x) (((x) > 0) ? (x) : (-(x)))
#define MOD 1000000007
#define pi acos(-1.0) using namespace std; typedef long long ll ;
typedef unsigned long long ull ;
typedef unsigned int uint ;
typedef unsigned char uchar ; template<class T> inline void checkmin(T &a,T b){if(a>b) a=b;}
template<class T> inline void checkmax(T &a,T b){if(a<b) a=b;} const double eps = 1e- ;
const int N = ;
const int M = * ;
const ll P = 10000000097ll ;
const double MINN = -999999999.9;
const int INF = 0x3f3f3f3f ;
const int MAXN = ; int root[MAXN];
struct Edge {
int from,to;
int w;
} edge[MAXN * MAXN]; int tol;
Edge ans[MAXN * MAXN];
int cnt; void addedge (int u, int v, int w) {
edge[tol].from = u;
edge[tol].to = v;
edge[tol].w = w;
++tol;
} bool cmp1 (Edge a, Edge b) {
if(a.w != b.w) return a.w < b.w;
else if (a.from != b.from) return a.from < b.from;
else return a.to < b.to;
} bool cmp2 (Edge a, Edge b) {
if (a.from != b.from) return a.from < b.from;
else return a.to < b.to;
} int find (int x) {
if (root[x] == -) return x;
return root[x] = find (root[x]);
} void kruscal () {
memset (root,-,sizeof(root));
cnt = ; //加入最小生成树的边
for (int k = ; k < tol; ++k) {
int u = edge[k].from;
int v = edge[k].to;
int t1 = find(u);
int t2 = find(v);
if(t1 != t2) {
ans[cnt++] = edge[k];
root[t1] = t2;
}
}
} int main () {
int T;
scanf("%d",&T);
int n;
while (T--) {
scanf ("%d",&n);
tol = ;
int w;
for (int i = ; i <= n; ++i) {
for (int j = ; j <= n; ++j) {
scanf("%d",&w);
if(j <= i || w == ) continue;
addedge(i, j, w);
}
}
sort (edge, edge + tol, cmp1);
kruscal ();
if (cnt != n - ) {
printf("-1\n");
continue;
} else {
sort (ans, ans + cnt, cmp2);
for (int i = ; i < cnt - ; ++i) {
printf("%d %d ", ans[i].from, ans[i].to);
}
printf("%d %d\n", ans[cnt - ].from, ans[cnt - ].to);
}
}
return ;
}