kru算法。
#include<iostream> #include<stdio.h> #include<string.h> #include<stdlib.h> using namespace std; int n,g[111][111]; class node { public: int u,v,len; }; int len; node edge[110000]; int pre[111]; void input() { for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) scanf("%d",&g[i][j]); len =0; for(int i=1;i<=n;i++) for(int j=1;j<i;j++) if(g[i][j]) { edge[++len].len =g[i][j]; edge[len].u =i<j?i:j; edge[len].v =i>j?i:j; } } int cmp1(const void *a,const void *b) { node *c =(node *)a; node *d= (node *)b; if(c->len >d->len ) return 1; if(c->len ==d->len &&c->u >d->u ) return 1; if(c->len ==d->len &&c->u ==d->u &&c->v >d->v ) return 1; return 0; } int cmp2(const void *a,const void *b) { node *c= (node *)a; node *d= (node *)b; if(c->u>d->u) return 1; if(c->u ==d->u &&c->v >d->v )return 1; return 0; } int find(int k) { if(k==pre[k]) return k; int t=find(pre[k]); pre[k]=t; return t; } void unin(int a,int b) { pre[b]=a; } void kru() { qsort(edge+1,len,sizeof(edge[1]),cmp1); int i,j,cnt=0; node ans[111]; for(i=1;i<=n;i++) pre[i]=i; for(i=1;i<=len;i++) { if(cnt==n-1) break; int f1=find(edge[i].u),f2=find(edge[i].v ); if(f1!=f2) { ans[++cnt]=edge[i]; unin(f1,f2); } } if(cnt!=n-1) { printf("-1\n"); return ; } qsort(ans+1,cnt,sizeof(ans[1]),cmp2); for(i=1;i<cnt;i++) printf("%d %d ",ans[i].u,ans[i].v ); printf("%d %d\n",ans[cnt].u,ans[cnt].v ); } int main() { int t; cin>>t; while(t--) { scanf("%d",&n); input(); kru(); } return 0; }