F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister 捐赠本站
Problem 3947. -- 无聊的大爷们

3947: 无聊的大爷们

Time Limit: 10 Sec  Memory Limit: 256 MB
Submit: 13  Solved: 5
[Submit][Status][Discuss]

Description

这是本次互测最水的一道题,希望大家珍惜机会。2015年的集训队的集训队互测就要开始了。大爷们的时间很宝贵
,每个人都有自己的安排。比如说A大爷要参加省选享受虐人的快感;B大爷刚好某天和他的某个妹子约好了要去XX
X;C大爷到外太空旅游去了,要过几天才回来,诸如此类。(为了保护当事人隐私权,所有人物名称皆为化名)问
题是,集训队互测的时间表和每天的出题人已经排好了。因为某种诡异的原因,时间被安排在了周末——意味着已
经无法修改互测的时间了。唯一的方法就是更改互测的顺序。不过这种事情难不倒集训队的大爷们,所以QQ群上经
常看到这样的对话:
``orz XXX大爷''
``orz,有什么事么?
''``4月20号我要去参加省选啊,我们换一下好不?''`
`我这边没问题,这就去换吧。''
本来事情就这样解决了,但是由于大爷们实在是太神了,所以互测时间总是换来
换去的。虽然大爷们对此毫不在意,但大爷们过于频繁的交换信息引发了庞大的信息爆炸,其总量超越了当今互联
网的物理容量的总和,最终瘫痪了整个信息社会,引发了全球人民的联名抗议。这下就有点麻烦了。只能要求大爷
们尽可能快地协商好了。这个问题也难不倒大爷们,通过大爷们的量子计算机对平行世界的观测,从未来带来了安
排好的时间表,所以只需要尽可能快地交换了。现在已知:1.开始安排的互测时间表,以及未来的互测时间表。2.
任意两个大爷交换互测时间所需时间为1s,会带来2^g[i][j]的信息量。若g[i][j]=-1则表明这两位大爷的交流产
生的信息量已经无法测定,即无穷大。3.一个大爷在一个时刻只可以进行一次交换,但是同一时刻可以发生许多交
换。4.为了拯救被崩溃的人类社会,希望能够得到一种安排,使得大爷们交换所占用的时间尽可能小。在占用时间
最小的前提下,请减小大爷们交换产生的总信息量。5.总信息量的计算公式为大爷每一次交换产生的所有信息量的
乘积。请2014年的您编程完成这个来自未来任务,拯救人类的未来吧!(若对题意有所疑惑,请仔细参考样例及样
例说明)

Input

首先输入n,表示2015年国家队候选人人数,大爷从1开始标号。接下来一行输入n个数{a[i]},表示开始安排的互
测时间表:a[i]表示第i次测试是由a[i]这位大爷。接下来一行输入n个数{b[i]},表示未来安排的互测时间表:b[
i]表示第i次测试是由大爷b[i]主持。保证a,b为排列。接下来一个n*n的矩阵,第i行第j列表示g[i][j],保证g[i
][j]=g[j][i]。但是对于任意i,g[i][i]不一定为0,意味着一旦大爷开始独自思考人生,世界将迎来末日。

Output

第一行输出一个整数,表示大爷交换的最小耗时,以秒为单位,具体见样例。接下来输出一个整数,表示在最小耗
时的前提下的最小信息量。为了减少您写高精度的负担,若答案为ans,请输出ans以2为底的对数,如果该信息量
无法测定,请输出-1。

Sample Input

样例输入1:
9
1 2 3 4 5 6 7 8 9
2 3 1 5 6 4 8 7 9
1 1 1 1 1 1 1 1 1
1 2 2 2 2 2 2 2 2
1 2 3 3 3 3 3 3 3
1 2 3 4 4 4 4 4 4
1 2 3 4 5 5 5 5 5
1 2 3 4 5 6 6 6 6
1 2 3 4 5 6 7 7 7
1 2 3 4 5 6 7 8 8
1 2 3 4 5 6 7 8 9
样例输入2:
1
1
1
-1
样例输入3:
2
1 2
2 1
1 2
2 1
样例输入4:
5
1 2 3 4 5
2 3 1 5 4
12 12 12 13 23
12 73 23 12 1
12 23 23 0 2
13 12 0 23 1
23 1 2 1 7
样例输入5:
8
1 2 3 4 5 6 7 8
2 3 4 1 6 7 8 5
2 2 2 2 1 1 1 1
2 2 2 2 1 1 1 1
2 2 2 2 1 1 1 1
2 2 2 2 1 1 1 1
1 1 1 1 2 2 2 2
1 1 1 1 2 2 2 2
1 1 1 1 2 2 2 2
1 1 1 1 2 2 2 2
样例输入6:
5
1 2 3 4 5
2 3 4 5 1
-1 -1 -1 -1 -1
-1 -1 -1 -1 -1
-1 -1 -1 -1 -1
-1 -1 -1 -1 -1
-1 -1 -1 -1 -1

Sample Output

样例输出1:
2
17
样例输出2:
0
0
样例输出3:
1
2
样例输出4:
2
25
样例输出5:
2
8
样例输出6:
2
-1

HINT


样例说明给定一个置换,我们总是可以将其拆成轮换的形式。

在样例2中,未来的顺序和现在的顺序没有区别,不

需要交换,故时间和最小信息量都为0。

在样例3中,我们只需要花费1s交换大爷1和大爷2,信息量为2,显然不存

在其它方案。

在样例4中,置换(2,3,1,5,4)可以分成两个轮换(1,2,3)(4,5),分别为长度为2和长度为3的轮换。显

然最小所需时间为2:第一秒交换(2,3)(4,5),第二秒交换(1,3)。不过信息量最小的方案却为第一秒交换(1,2

)(4,5),第二秒(3,1)在样例5中,给定的是两个长度为4的轮换。最小所需时间依旧为2,因为我们既可以第一

秒交换(1,4)(2,3)第二秒交换(2,4)完成一个轮换,亦可以在第一秒交换(2,4)第二秒交换(1,2)(3,4)

。无论哪种的最小信息量都为2*2*3=12。但是如果我们第一秒交换(1,5)(2,8)(3,7)(4,6),第二秒交换(

1,6)(2,5)(3,8)(4,7),所需要的最小信息量为8。在样例6中,给定的是一个长度为5的轮换,最小所需时

间依旧为2,因为我们可以第一秒交换(2,5)(3,4),第二秒交换(1,2)(3,4)完成轮换。显然第二问的答案

为-1。数据规模和约定考虑两个轮换A,B,若存在A中某元素与B中某元素交换的代价不为-1,在A,B之间连一条边。

数据保证:n<=100,0<=g[i][j]<=10000或g[i][j]=-1


Source

2014年国家集训队十五人互测

[Submit][Status][Discuss]

HOME Back