#2615. 超级斗兽棋
超级斗兽棋
题目描述
斗兽棋是一项有趣的棋类游戏。双方分别控制一些动物,在棋盘上按照一定的规则轮流行动,先占领对方巢穴为胜。任意两种不同的动物A和B相遇,要么A胜B,要么B胜A。 不过,原先的斗兽棋中动物种类较少,玩久了就会略显无聊。于是,某公司决定开发一种超级斗兽棋,含有N种动物,编号为1,2,……,N,并已经制定好了任意两种不同动物相遇时的胜负关系。 下一步工作是测试超级斗兽棋的趣味性。经调查发现,若动物间相互制约,则游戏的趣味性将大大增加。所谓动物间相互制约,即可以将动物按某种次序排成一个序列P1,P2,……,Pn,满足P1胜P2,P2胜P3,……,P(n-1)胜Pn,Pn胜P1。如果动物间不能相互制约,但可以半相互制约(在相互制约的条件中去掉“Pn胜P1”,其他条件不变)的话,那么这款游戏虽然趣味性有所降低,但勉强可以接受。不过,如果连半相互制约都不能满足的话,呵呵,对不起,重新设计吧。 你的任务就是帮助测试这款超级斗兽棋的趣味性。
输入格式
第一行是一个整数n,表示动物种类数。接下来是一个n*n的矩阵,为动物间的胜负关系,第i行第j列为1则i胜j,为0则j胜i(保证胜负关系不会矛盾,即不同的i和j相遇有且仅有一个胜者;主对角线上全为0)。 第一行是一个整数s,表示测试结果:0表示动物间相互制约,1表示动物间不相互制约但半相互制约,-1表示都不满足。若测试结果不为-1,则在第二行输出满足响应条件的任一序列P(即测试结果为0时输出满足相互制约条件的序列,为1时输出半相互制约条件的序列)。
输出格式
5 0 0 1 1 1 1 0 1 1 0 0 0 0 1 0 0 0 0 0 1 0 1 1 0 0
0
1 3 4 5 2
提示
100%的数据,2<=n<=200 请不要提交,期待SPJ
题目来源
没有写明来源