| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 1522 人关注过本帖
标题:图论问题------大家过来看看
只看楼主 加入收藏
crackerwang
Rank: 3Rank: 3
等 级:新手上路
威 望:8
帖 子:833
专家分:0
注 册:2007-2-14
收藏
 问题点数:0 回复次数:7 
图论问题------大家过来看看



Take a walk

Time Limit:1000MS Memory Limit:65536K
Total Submit:115 Accepted:26

Description

  TheBeet和一个MM在一个TheBeet常去的公园里面散步。TheBeet对这个公园的每个景点和每个景点之间连接的路都很熟悉,但是这个MM是第1次来,她对这个公园的每条路上的景点都很好奇。
  现在他们俩在公园的1号景点(其实就是公园的大门 -_-|||),到了一个景点后,MM会随机的选取1条他们没有走过的路,直到他们无路可走。
  TheBeet研究了一下公园的地图,然后告诉MM说无论她每次怎么选择,他们都能逛完公园所有的路和景点然后回到起点。这个MM很聪明,TheBeet告诉她公园所有景点和每个景点的连接情况后,她一下子就知道TheBeet是否在撒谎。

Input

输入包含多组测试数据。每组测试数据用一个空行隔开。
每个测试数据的第一行是两个整数 n, m开始,(1 <= n <= 100, 0 <= m <= 10000) 表示这个公园包含的景点数和道路数目,景点以1..n标号。
接下来是m行每行包含2个数字,表示这条道路所连接的景点。
n = m = 0代表输入结束。

Output

对于每个测试点,先输出"Case #:",#代表第几个测试点,然后在下一行输出"Yes." 或 "TheBeet lies."(不包含引号)来表示TheBeet所说的话是真是假。

Sample Input

7 8
1 2
2 3
3 1
1 4
4 5
5 6
6 7
7 1

5 6
1 2
2 3
1 4
2 4
2 5
3 5

0 0

Sample Output

Case 1:
Yes.
Case 2:
TheBeet lies.

Hint

对于Case 2,假如MM选择了 1 --> 2 --> 4 --> 1 这样的路,那么他们就无路可走了。

Source

XMU Warm Up

提交地点:http://59.77.14.110/JudgeOnline/showproblem?problem_id=1168
完全没有思路...大家一起来讨论一下..高手给分析一下..谢谢

搜索更多相关主题的帖子: 图论 公园 景点 align 
2007-10-26 20:31
crackerwang
Rank: 3Rank: 3
等 级:新手上路
威 望:8
帖 子:833
专家分:0
注 册:2007-2-14
收藏
得分:0 
自己先顶一下..做了有一断时间了...
后来没有办法直接问了出这个题目的人the beet..他不甩我...我很不爽

2007-10-26 20:47
chmlqw
Rank: 1
等 级:新手上路
帖 子:180
专家分:0
注 册:2007-10-11
收藏
得分:0 

一个无向连通图是欧拉图的的充分必要条件是:该图的顶点次数都是偶数
这个题目其实就是判断是不是欧拉图

2007-10-27 12:14
卧龙孔明
Rank: 9Rank: 9Rank: 9
等 级:贵宾
威 望:59
帖 子:3872
专家分:684
注 册:2006-10-13
收藏
得分:0 
希望楼主将原题测试地址贴出
(除了TJ的外我还没看过中文ACM-OJ)

给楼主一个思路:这是"一笔画"问题,实质是找
是否有2个以上的奇数点,如果有,则No,return
如果否,则继续判断是否开始处于奇数点处,如果非,则No,return
如果否,则继续判断是否只有1个奇数点,如果是,则No,return
如果否,则Yes

My Blog: www.aiexp.info
虽然我的路是从这里开始的,但是这里不再是乐土.感谢曾经影响过,引导过,帮助过我的董凯,飞燕,leeco,starwing,Rockcarry,soft_wind等等等等.别了,BCCN.
2007-10-27 15:14
crackerwang
Rank: 3Rank: 3
等 级:新手上路
威 望:8
帖 子:833
专家分:0
注 册:2007-2-14
收藏
得分:0 
以下是引用chmlqw在2007-10-27 12:14:36的发言:

一个无向连通图是欧拉图的的充分必要条件是:该图的顶点次数都是偶数
这个题目其实就是判断是不是欧拉图

不对..你没有仔细分析..题目不是要判断欧拉图...
欧拉图的定义是是否存在一个走法使得经过所有的路仅且一次在回到原来的地方..和这个题目有很大的区别...


2007-10-27 16:47
crackerwang
Rank: 3Rank: 3
等 级:新手上路
威 望:8
帖 子:833
专家分:0
注 册:2007-2-14
收藏
得分:0 
以下是引用卧龙孔明在2007-10-27 15:14:30的发言:
希望楼主将原题测试地址贴出
(除了TJ的外我还没看过中文ACM-OJ)

给楼主一个思路:这是"一笔画"问题,实质是找
是否有2个以上的奇数点,如果有,则No,return
如果否,则继续判断是否开始处于奇数点处,如果非,则No,return
如果否,则继续判断是否只有1个奇数点,如果是,则No,return
如果否,则Yes

XMU Warm Up

提交地点:http://59.77.14.110/JudgeOnline/showproblem?problem_id=1168


2007-10-27 16:48
crackerwang
Rank: 3Rank: 3
等 级:新手上路
威 望:8
帖 子:833
专家分:0
注 册:2007-2-14
收藏
得分:0 
别沉了..

2007-10-28 16:52
vvian00
Rank: 1
等 级:新手上路
帖 子:1
专家分:0
注 册:2009-7-26
收藏
得分:0 
可是楼主,难道这不是在经典不过的,一笔画问题么???
2009-07-26 22:12
快速回复:图论问题------大家过来看看
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.015903 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved