ZOJ 3204 Connect them

Connect them


Time Limit: 1 Second      Memory Limit: 32768 KB


You have n computers numbered from 1 to n and you want to connect them to make a small local area network (LAN). All connections are two-way (that is connecting computers i and j is the same as connecting computers j and i). The cost of connecting computer i and computer j is cij. You cannot connect some pairs of computers due to some particular reasons. You want to connect them so that every computer connects to any other one directly or indirectly and you also want to pay as little as possible.

Given n and each cij , find the cheapest way to connect computers.

Input

There are multiple test cases. The first line of input contains an integer T (T <= 100), indicating the number of test cases. Then T test cases follow.

The first line of each test case contains an integer n (1 < n <= 100). Then n lines follow, each of which contains n integers separated by a space. The j-th integer of the i-th line in these n lines is cij, indicating the cost of connecting computers i and j (cij = 0 means that you cannot connect them). 0 <= cij <= 60000, cij = cjicii = 0, 1 <= ij <= n.

Output

For each test case, if you can connect the computers together, output the method in in the following fomat:

i1 j1 i1 j1 ......

where ik ik (k >= 1) are the identification numbers of the two computers to be connected. All the integers must be separated by a space and there must be no extra space at the end of the line. If there are multiple solutions, output the lexicographically smallest one (see hints for the definition of "lexicography small") If you cannot connect them, just output "-1" in the line.

Sample Input

2
3
0 2 3
2 0 5
3 5 0
2
0 0
0 0

Sample Output

1 2 1 3
-1

Hints: A solution A is a line of p integers: a1a2, ...ap. Another solution B different from A is a line of q integers: b1b2, ...bq. A is lexicographically smaller than B if and only if: (1) there exists a positive integer r (r <= pr <= q) such that ai = bi for all 0 < i < r and ar < br OR

(2) p < q and ai = bi for all 0 < i <= p

最小生成树:

#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
#include <math.h>
#include <stdio.h>

using namespace std;
const int INF=1e5;
struct Node
{
    int x;int y;
    int value;
}a[10005];
int cmp(Node a,Node b)
{
    if(a.value==b.value)
    {
        if(a.x==b.x)
        {
            return a.y<b.y;
        }
        return a.x<b.x;
    }
    else
        return a.value<b.value;
}
struct node
{
    int x;
    int y;
}ans[INF+5];
int cmp2(node a,node b)
{
    if(a.x==b.x)
        return a.y<b.y;
    else
        return a.x<b.x;
}
int n;
int father[INF+5];
int find(int x)
{
    if(father[x]!=x)
        father[x]=find(father[x]);
    return father[x];
}

int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        int tot=0;
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                scanf("%d",&a[++tot].value);
                a[tot].x=i;
                a[tot].y=j;
                if(a[tot].value==0)
                    a[tot].value=INF;
            }
        }
        sort(a+1,a+tot+1,cmp);
        for(int i=1;i<=n;i++)
            father[i]=i;
        int cot=0;
        for(int i=1;i<=tot;i++)
        {
            if(a[i].value==INF)
                continue;
            int xx=find(a[i].x);
            int yy=find(a[i].y);
            if(xx!=yy)
            {
                father[xx]=yy;
                ans[++cot].x=a[i].x;
                ans[cot].y=a[i].y;
            }
        }
        int root=find(1);
        bool res=true;
        for(int i=2;i<=n;i++)
        {
            find(i);
            if(father[i]!=root)
                res=false;
        }
        if(!res)
            printf("-1\n");
        else
        {
            sort(ans+1,ans+1+cot,cmp2);
            for(int i=1;i<=cot;i++)
            {
                if(i==cot)
                    printf("%d %d\n",ans[i].x,ans[i].y);
                else
                    printf("%d %d ",ans[i].x,ans[i].y);
            }
        }
        
        
    }
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏北京马哥教育

Python高级编程技巧

正文: 本文展示一些高级的Python设计结构和它们的使用方法。在日常工作中,你可以根据需要选择合适的数据结构,例如对快速查找性的要求、对数据一致 性的要求或...

4324
来自专栏机器学习与自然语言处理

04-树6. Huffman Codes--优先队列(堆)在哈夫曼树与哈夫曼编码上的应用

题目来源:http://www.patest.cn/contests/mooc-ds/04-%E6%A0%916 In 1953, David A. Huffm...

2757
来自专栏小樱的经验随笔

POJ 3278 Catch That Cow(BFS,板子题)

Catch That Cow Time Limit: 2000MS Memory Limit: 65536K Total Submissions...

2975
来自专栏轻扬小栈

[半zz]迅雷笔试题

1693
来自专栏计算机视觉与深度学习基础

Leetcode 154 Find Minimum in Rotated Sorted Array II

Follow up for "Find Minimum in Rotated Sorted Array": What if duplicates are a...

1856
来自专栏C语言及其他语言

[每日一题]C语言程序设计教程(第三版)课后习题6.1

题目描述 输入两个正整数m和n,求其最大公约数和最小公倍数。 输入 两个整数 输出 最大公约数,最小公倍数 样例输入 5 7 样例输出 1 35 提示 此类题目...

3153
来自专栏大内老A

这是EnterLib PIAB的BUG吗?

在默认的情况下,EnterLib的PIAB采用基于TransparentProxy/RealProxy的机制实现对方法调用的拦截,进而实现了对横切关注点(Cro...

2096
来自专栏小樱的经验随笔

AtCoder Beginner Contest 069【A,水,B,水,C,数学,D,暴力】

A - K-City ---- Time limit : 2sec / Memory limit : 256MB Score : 100 points Prob...

5144
来自专栏数据结构与算法

BZOJ1901: Zju2112 Dynamic Rankings(整体二分 树状数组)

给定一个含有n个数的序列a[1],a[2],a[3]……a[n],程序必须回答这样的询问:对于给定的i,j,k,在a[i],a[i+1

842
来自专栏技术碎碎念

LeetCode-1- Two Sum

Given an array of integers, return indices of the two numbers such that they add...

2948

扫码关注云+社区

领取腾讯云代金券