主要就是将最小生成树的边按字典序输出。
读取数据时，把较小的端点赋给u，较大的端点号赋值给v。 这里要用两次排序，写两个比较器： 第一次是将所有边从小到大排序，边权相同时按u从小到大，u相同时按v从小到大，用kruskal求出最小生成树。 第二次将求出的最小生成树的边在排序，这次只要按u、v从小到大排序即可。
#include <algorithm>
#include <cstring>
#include <cstdio> using namespace std; int index1;
int n,cost,idx,t;
int ans; struct Edge{
int u,v;
int cost; }edge[],MST[]; struct UF{
int father[]; void unit(){
for(int i=;i<=n;i++){
father[i]=i;
}
} int find_root(int x){
if(father[x]!=x)
father[x]=find_root(father[x]);
return father[x];
} void Union(int fa,int fb){
father[fb]=fa;
}
}uf; bool cmp1(const Edge t1,const Edge t2){
if(t1.cost!=t2.cost)
return t1.cost<t2.cost;
if(t1.u!=t2.u)
return t1.u<t2.u;
else
return t1.v<t2.v;
} bool cmp2(const Edge t1,const Edge t2){
if(t1.u!=t2.u)
return t1.u<t2.u;
else
return t1.v<t2.v;
} int main()
{
scanf("%d",&t);
for(int q=;q<t;q++){
scanf("%d",&n);
index1=;
for(int i=;i<=n;i++){
for(int j=;j<=i;j++)
scanf("%d",&cost);
for(int j=i+;j<=n;j++){
scanf("%d",&cost);
if(cost!=){
edge[index1].u=i;
edge[index1].v=j;
edge[index1].cost=cost;
index1++;
}
}
} sort(edge,edge+index1,cmp1);
uf.unit();
int count=;
idx=; for(int i=;i<index1;i++){
int u=edge[i].u;
int v=edge[i].v;
int fu=uf.find_root(u);
int fv=uf.find_root(v);
if(count==n-){
break;
}
if(fu!=fv){
MST[idx].u=u;
MST[idx].v=v;
MST[idx].cost=cost;
idx++;
count++;
uf.Union(fu,fv);
}
}
if(count<n-){
printf("-1\n");
}
else{
sort(MST,MST+idx,cmp2);
for(int i=;i<idx;i++){
//果真要按照下面的输入，否则为presentation error 。。。
if(i==)
printf("%d %d",MST[i].u,MST[i].v);
else
printf(" %d %d",MST[i].u,MST[i].v);
}
printf("\n");
}
}
return ;
}