题目名称 1720. 二分图游戏
输入输出 graphgame.in/out
难度等级 ★★☆
时间限制 1000 ms (1 s)
内存限制 256 MB
测试数据 20 简单对比
题目来源 2014-10-03
开放分组 全部用户
提交状态
分类标签
通过:72, 提交:270, 通过率:26.67%
GravatarPepcy_Ch 100 0.047 s C++
GravatarAntiLeaf 100 0.084 s C++
Gravatar哒哒哒哒哒! 100 0.085 s C++
GravatarAAAAAAAAAA 100 0.096 s C++
GravatarShirry 100 0.096 s C++
GravatarShirry 100 0.096 s C++
Gravatar‎MistyEye 100 0.098 s C++
Gravatar_Itachi 100 0.121 s C++
GravatarHzoi_moyi 100 0.121 s C++
Gravatar沉迷学习的假的Keller 100 0.128 s C++
关于 二分图游戏 的讨论
比赛的时候看错题了,把删点看成删边……成功GG
Orz主DPS @武嘉鑫
Gravatarcstdio
2014-10-03 22:39 1楼
回复 @cstdio :
Orzzzzz......我记得这题看错是我误导的QAQ
GravatarAsm.Def
2014-10-05 09:00 2楼
回复 @william :
Orzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz主DPS
GravatarChenyao2333
2014-10-05 12:04 3楼
Gravatarstdafx.h
2015-08-25 10:37 4楼
我就是阿拉巴拉巴拉
Gravatar_stranger
2015-08-26 16:14 5楼
Gravatar啊吧啦吧啦吧
2015-08-28 14:12 6楼
VIP 一不小心刷榜成功...然而并无任何优化...
Gravatar沉迷学习的假的Keller
2016-04-04 20:20 7楼
匈牙利
GravatarShirry
2017-03-23 00:21 8楼
你们都好神啊
GravatarRapiz
2017-03-23 00:58 9楼
回复 @Rapiz :
哪有您神orz
GravatarShirry
2017-03-23 01:08 10楼

1720. 二分图游戏

★★☆   输入文件:graphgame.in   输出文件:graphgame.out   简单对比
时间限制:1 s   内存限制:256 MB

【题目描述】

Nick和Peter在参加计算复杂性理论讲座的时候喜欢玩如下的游戏。他们在一张纸上画出一个无向的二分图G,并在一个顶点放上棋子。之后他们轮流走棋子。Nick先走。

每一步都是将棋子沿着图中的一条边移动。之后,在这一步之前棋子所在的顶点,偕同与之相连的所有边,都被从图中删去。没有边可走的玩家输掉游戏。

给出Nick和Peter画出的图。对图中的每个顶点,计算如果最初将棋子放在这里,谁将会赢。假设Nick和Peter都执行最优策略。

【输入格式】

输入文件的第一行有三个整数n1,n2,m——分别代表二分图左边的顶点数,右边的顶点数,和边数。1<=n1,n2<=500,0<=m<=50000.

接下来m行描述了这些边。每一行有两个数,即该边所连接的左顶点和右顶点。两边的顶点都从1开始标号。

【输出格式】

输出两行。第一行有n1个字符,如果最初把棋子放在左边的第i个顶点,Nick会赢,第i个字符就是'N',如果Peter会赢就是'P'。第二行以相同的格式输出n2个字符,描述右边n个顶点的必胜者。

【样例输入】

3 3 5

1 1

1 2

1 3

2 1

3 1

【样例输出】

NPP

NPP

【来源】

Andrew Stankevich Contest 21

acdream 1403 Graph Game