最小生成树，我用的是并查集+贪心的写法。

 

#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;const int maxn = 111;int c[maxn][maxn];int father[maxn];int flag[maxn];struct abc{    int fei, a, b;}dt[maxn*maxn];struct ans{    int aa, bb;}anss[maxn*maxn];bool cmp(const abc&a, const abc&b){    if (a.fei == b.fei&&a.a == b.a) return a.b < b.b;    if (a.fei == b.fei) return a.a < b.a;    return a.fei < b.fei;}bool cmp2(const ans&a, const ans&b){    if (a.aa == b.aa) return a.bb < b.bb;    return a.aa < b.aa;}int find(int x){    if (x != father[x]) father[x] = find(father[x]);    return father[x];}int main(){    int sb;    scanf("%d", &sb);    while (sb--)    {        int n, i, j;        scanf("%d", &n);        memset(c, 0, sizeof(c));        memset(father, 0, sizeof(father));        memset(flag, 0, sizeof(flag));        int q = 0;        for (i = 0; i <= 100; i++) father[i] = i;        for (i = 1; i <= n; i++) for (j = 1; j <= n; j++) scanf("%d", &c[i][j]);        for (i = 1; i <= n; i++)        {            for (j = i + 1; j <= n; j++)            {                if (c[i][j] != 0)                {                    dt[q].a = i;                    dt[q].b = j;                    dt[q].fei = c[i][j];                    q++;                }            }        }        sort(dt, dt + q, cmp);        int qq = 0;        for (i = 0; i < q; i++)        {            int x = find(dt[i].a);            int y = find(dt[i].b);            if (x != y)            {                father[x] = y;                anss[qq].aa = dt[i].a;                anss[qq].bb = dt[i].b;                qq++;            }        }        for (i = 1; i <= n; i++){
   int u = find(i);flag[u]++;}        int dd = 0;        for (i = 1; i <= n; i++){
   if (flag[i] > 0 && flag[i] == n){dd = 1;break;}}        if (dd==1)        {            sort(anss, anss + qq, cmp2);            for (i = 0; i < qq; i++)            {                if (i < qq-1)printf("%d %d ", anss[i].aa, anss[i].bb);                else printf("%d %d\n", anss[i].aa, anss[i].bb);            }        }        else if (dd == 0) printf("-1\n");    }    return 0;}