Connect them

  1 /*
  2 zoj3204 
  3 
  4 
  5 解题思路：
  6 赤裸裸的最小生成树。只是要求输出字典序最小的连接方案。
  7 所以在边的排序时要注意了，有可能存在边的权值是相同的边。
  8 所以在这种情况下，要按他们的顶点序列排序。直接把STL搬上了，很好很强大。 */ 
  9 #include<iostream>
 10 #include<cstdio>
 11 #include<iostream>
 12 #include <stdio.h>
 13 #include <stdlib.h>
 14 #include <cstdio>
 15 #include <cstring>
 16 #include<cmath>
 17 #include<algorithm>
 18 using namespace std;//这句写的时候千万别丢，不然许多函数无法使用 
 19 const int MAX=110; 
 20 struct Node{
 21     int from, to;
 22     int w;
 23     
 24 }edge[MAX*MAX];//记录读取时边的端点和权值 
 25 
 26 Node ans[MAX*MAX];//记录构成最小生成树里面的边 （边端点） 
 27 int n;//点的个数 
 28 int fa[MAX];// 并查集的 
 29 int tol;//记录最小生成树边的个数 
 30 int cnt;//记录ans里的边的个数 
 31  void addedge(int u ,int v,int w){
 32      edge[tol].from=u;
 33      edge[tol].to=v;
 34      edge[tol].w=w;
 35      tol++;
 36      
 37  }//添加边额操作 
 38 void makeset(){
 39     for(int i=1;i<=n;i++){
 40     fa[i]=i;    
 41         
 42     }
 43     
 44 }//并查集的初始化 ，也可以直接初始化为-1 
 45 int Find(int x){
 46     while(x!=fa[x])
 47     x=fa[x];
 48     return x;
 49 }//并查集的查找操作 
 50 void uion(int x,int y){
 51     int a=Find(x);
 52     int b=Find(y);
 53     if(a!=b){
 54         ans[cnt].from=x;
 55         ans[cnt].to=y;
 56         cnt++;
 57         fa[a]=b;
 58         }
 59     
 60     }//并查集的合并操作 
 61 int cmp1(Node a,Node b){
 62     if(a.w!=b.w)return a.w<b.w;
 63     else {if(a.from==b.from)
 64         
 65     
 66           return a.to<b.to;
 67           else
 68           return a.from<b.from;
 69     }
 70 }//比较器首先按w从小到大排序，若w相等，则依次按照from，to进行排序 ，这是给边排序 
 71 int cmp2(Node a,Node b){
 72     
 73     if(a.from!=b.from)return a.from<b.from;
 74     else
 75     return a.to<b.to;
 76 }//这个比较器主要是给ans里面的边排序，使其按照要求输出 
 77 int main(){
 78     int t;
 79     scanf("%d",&t);
 80     while(t--){
 81         scanf("%d",&n);
 82         tol=0;
 83         cnt=0;//一定要在该处初始化tol，cnt否则会报超时的错误 
 84        makeset();
 85        int d;
 86         for(int i=1;i<=n;i++){
 87             
 88             for(int j=1;j<=n;j++){
 89                 scanf("%d",&d);
 90                 if(j<=i)continue;
 91                 if(d==0)continue;//这样读取会使避免重边的影响 
 92                 addedge(i,j,d);//前面的d会被后面的覆盖 
 93                 
 94             }
 95         }
 96         sort(edge,edge+tol,cmp1);//排序 
 97         for(int i=0;i<tol;i++)
 98              uion(edge[i].from,edge[i].to);
 99         
100         sort(ans,ans+cnt,cmp2);
101         if(cnt!=n-1){
102         printf("-1
");
103         continue;}//这一步很重要，是判断能不能形成最小生成树的 
104         else{
105             
106         
107         for(int i=0;i<cnt-1;i++){
108             printf("%d %d ",ans[i].from,ans[i].to);//注意题目给出的输出格式 
109             }
110             printf("%d %d
",ans[cnt-1].from,ans[cnt-1].to);
111             
112     }
113     }
114     
115 }