Skip to content

14063: 【原4063】Pets

题目

题目描述

author: xxxxxyt 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4063

Description

时间限制: 1500 ms

空间限制: 512 MiB

xxxxxyt学姐经常一个人在寝室,难免会感到寂寞,于是学姐养了 n 只可爱的宠物,比如皮皮虾、大蟒蛇、藏狐、安康鱼…但即便如此学姐还是感到无聊。突然有一天,学姐想到了让宠物们互相对战的消遣方法(请不要给动物保护协会打电话)。学姐让宠物们两两进行对战,\(n\times (n-1)/2\) 场对战后,学姐得到了一张相生相克图,然后又根据自己的喜好,把宠物们分成了一队与二队。就在队伍分好后,学姐的强迫症又犯了,她希望自己的两支队伍都满足这样一个性质:存在某种排列,使得排在后面的宠物能够击败排在前面的所有宠物。但学姐的懒惰大家都是知道的,所以她找到了你,希望你能告诉她这两支队伍是否均满足要求,如果是,她还希望你告诉她最多可以从二队中抽出多少只宠物放在一队,使得两支队伍仍然满足要求。努力解决问题吧,而xxxxxyt学姐,瘫躺。

input format

第一行输入两个数字 n 和 m,分别表示学姐有 n 只宠物,其中被分到一队的宠物有 m 只。

​接下来 n 行每行 n 个数字,\(a(i,j)\in {0,1}\)表示第 i 只宠物是否能战胜第 j 只宠物,保证\(a(i,i)=0\)且\(a(i,j)\neq a(j,i)\)。

接下来一行 m 个数字,表示有哪些宠物被分到了一队。

output format

如果两支队伍均不能让xxxxxyt满意,则输出NO;否则输出YES,并输出一个最大的 k ,使得从二队中非任意地抽出 k 只宠物放入一队后,两支队伍仍然满足条件。详细格式见样例输出。

sample input1

3 2
0 1 1
0 0 1
0 0 0
3 1

sample output1

YES 1

sample input2

4 3
0 1 0 1
0 0 1 1
1 0 0 1
0 0 0 0
1 2 3

sample output2

NO

sample input3

4 2
0 1 0 1
0 0 1 1
1 0 0 1
0 0 0 0
1 2

sample output3

YES 1

limits

注意:

  • 宠物们的实力是相对的,也就是可能会出现A战胜B,B战胜C,C又战胜A的情况。
  • 数据范围较大, 建议使用scanf读入

数据范围:

  • 20% 的数据 1 <= m < n <= 10
  • 60% 的数据 1 <= m < n <= 100
  • 100% 的数据 1 <= m < n <= 3000

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!