HDU 5811 Colosseo （拓扑排序+LIS）

HDU 5811 Colosseo （拓扑排序+LIS）

Colosseo

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 530    Accepted Submission(s): 15

Problem Description

Mr. Chopsticks keeps N monsters, numbered from 1 to N. In order to train them, he holds N * (N - 1) / 2 competitions and asks the monsters to fight with each other. Any two monsters fight in exactly one competition, in which one of them beat the other. If monster A beats monster B, we say A is stronger than B. Note that the “stronger than” relation is not transitive. For example, it is possible that A beats B, B beats C but C beats A. After finishing all the competitions, Mr. Chopsticks divides all the monsters into two teams T1 and T2, containing M and N – M monsters respectively, where each monster is in exactly one team. Mr. Chopsticks considers a team of monsters powerful if there is a way to arrange them in a queue (A1, A2, …, Am) such that monster Ai is stronger than monster Aj for any 1<=i

Input

The input contains multiple test cases. Each case begins with two integers N and M (2 <= N <= 1000, 1 <= M < N), indicating the number of monsters Mr. Chopsticks keeps and the number of monsters in T1 respectively. The following N lines, each contain N integers, where the jth integer in the ith line is 1 if the ith monster beats the jth monster; otherwise, it is 0. It is guaranteed that the ith integer in the jth line is 0 iff the jth integer in the ith line is 1. The ith integer in the ith line is always 0. The last line of each case contains M distinct integers, each between 1 and N inclusively, representing the monsters in T1. The input is terminated by N = M = 0.

Output

For each case, if both T1 and T2 are powerful, output “YES” and the maximum k; otherwise, output “NO”.

Sample Input

3 2

0 1 1

0 0 1

0 0 0

3 1

4 3 0

1 0 1

0 0 1

1 1 0

0 1 0 0

0 0 1 2

3 4 2 0

1 0 1 0 0

1 1 1 0 0

1 0 0 0 0

1 2 0 0

Sample Output

YES 1 NO YES 1

Hint

In the third example, Mr. Chopsticks can let the monster numbered 4 from T2 join into T1 to form a queue (1, 2, 4).

Author

SYSU

Source

​​2016 Multi-University Training Contest 7​​

Recommend

wange2014   |   We have carefully selected several similar problems for you:  ​​5831​​​ ​​5830​​​ ​​5829​​​ ​​5828​​​ ​​5827​​

题意：有n只怪兽，让他们互相打一次，用n X n矩阵表示，在i th 行，j th列是1，就是怪兽 i 打爆了怪兽 j。

但这些关系没有传递性。比如不存在A能打败B ，B能打败C ，C能打败A的情况。

现在挑选出m只怪兽组成T1队，剩下n-m只怪兽组成T2队。 问你T1队与T2队是否存在某种排列 a1,a2,a3,...,ak ，使任意一只怪兽都能打败他右边所有怪兽。存在就YES，否则就NO。

如果输出的是YES。就在问你最多能从T2中能选出多少只怪兽插入到T1中，同样能满足上面的情况。

题解：（卡常数题，用gets才过）

第一问：可以用toposort来解决。

第二问：如果是YES，可以在拓扑排序中找到T1和T2的拓扑序列。在T2的拓扑序列中从低到高（最弱的怪兽到能打败T2中所有怪兽的怪兽）遍历，在T1中找到它可以放置的位置，并且这个位置是唯一的！否则就不能插入T1。

然后标上T2在T1中的位置值，对得到的这个位置值数列，求最长上升子序列的长度就是答案. 总复杂度O(N^2)。

官方题解：

判断YES或NO的时候拓扑排序或者暴力O(N^2)判断都可以. 接下来对于T2中的每个点，只需要在T1中扫一遍就可以判断出是否可以放进T1，如果不能放进去就直接丢掉，如果可以就确定放在哪个位置. 注意因为是个竞赛图，所以这个位置是唯一的. 给T2剩下的点按在T2中的拓扑顺序（因为是竞赛图，所以这个顺序也是唯一的）标上它们在T1中的位置值，对得到的这个位置值数列求最长上升子序列的长度就是答案. 总复杂度O(N^2).

AC代码：

#include#include#include#include#include#include#include#include

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。