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 iand 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 = cji, cii = 0, 1 <= i, j <= 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: a1, a2, ...ap.
Another solution B different from A is a line of q integers: b1, b2, ...bq.
A is lexicographically smaller than B if and only if:
(1) there exists a positive integer r (r <= p, r <= 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
Author: CAO, Peng
Source: The 6th Zhejiang Provincial Collegiate Programming Contest
#include <iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
using namespace std;
int t,n;
int team[];
bool flag;
struct node
{
int x,y,cost;
node(int a,int b,int c){x=a;y=b;cost=c;}
};
struct cmp
{
bool operator()(node a,node b)
{
if (a.cost!=b.cost) return a.cost>b.cost;
else if (a.x!=b.x) return a.x>b.x;
else return a.y>b.y;
}//wa了一发,原因在这,只排了cost,没有考虑到如果cost相等应该也要先考虑字典序小的。
};
struct cmp2
{
bool operator()(node a,node b)
{
if (a.x!=b.x) return a.x>b.x;
else if (a.y!=b.y) return a.y>b.y;
}
};
int findteam(int k)
{
if (team[k]!=k) return team[k]=findteam(team[k]);
else return k;
}
int main()
{
while(~scanf("%d",&t))
{
for(;t>;t--)
{
scanf("%d",&n);
int l=;
priority_queue<node,vector<node>,cmp>Q;
priority_queue<node,vector<node>,cmp2>QQ;
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
{
int x;
scanf("%d",&x);
if (j>i && x!=)
Q.push(node(i,j,x));
}
for(int i=;i<=n;i++) team[i]=i;
flag=;
while(!Q.empty())
{
node u=Q.top();
Q.pop();
int teamx=findteam(u.x);
int teamy=findteam(u.y);
if (teamx!=teamy)
{
team[teamy]=teamx;
QQ.push(u);
}
int k=findteam();
flag=;
for(int i=;i<=n;i++)
if (k!=findteam(i)) {flag=; break;}
if(flag) break;
}
if (!flag) printf("-1\n");
else
{
int i=;
while(!QQ.empty())
{
node u=QQ.top();
QQ.pop();
if (i++) printf(" ");
printf("%d %d",u.x,u.y);
}
printf("\n");
}
}
} return ;
}
最新文章
- ZeroMq安装包的生成【ubuntu10】
- 未签名有元程序集 Unsigned Friend Assemblies
- javaScript入门第一天
- IOS 蓝牙相关-BabyBluetooth蓝牙库介绍(4)
- 为Ubuntu Server安装gnome图形桌面环境
- C#堆栈和托管堆
- [leetcode]_Valid Sudoku
- 使用GDataXML解析XML文档
- C# asp Aspose.Cells 教程,包含增加勾选框,单元格,字体设置
- 使用CURL出现certificate verify failed错误的解决方法
- 任正非:华为三十年大限快到了 想不死就得新生(建立战略预备队)cool
- ps2keyboard demo code for 8052
- POCO系列之——延迟加载
- iOS开发——工厂模式
- Lumen框架—升级改造之路-仓储层
- 全面剖析XMLHttpRequest对象
- C++ Opencv split()通道分离函数 merge()通道合并函数 使用操作详解
- rem移动端适配方案
- jsp中添加过滤器,实现校验用户身份
- nginx——Nginx 防爬虫优化