推荐做那个的电影网站,浙江建筑网站,上海seo搜索优化,网站建设中数据库题目链接 题意 #xff1a; 庄园有很多房间#xff0c;编号从0到n-1,能否找到一条路径经过所有开着的门#xff0c;并且使得通过门之后就把门关上#xff0c;关上的再也不打开#xff0c;最后能回到编号为0的房间。 思路 #xff1a; 这就是一个赤裸裸的判断欧拉通路的问…题目链接 题意 庄园有很多房间编号从0到n-1,能否找到一条路径经过所有开着的门并且使得通过门之后就把门关上关上的再也不打开最后能回到编号为0的房间。 思路 这就是一个赤裸裸的判断欧拉通路的问题了但实际上就只有两种情况能够输出YES以房间为顶点连接房间之间的门为边构造图这两种情况分别是存在欧拉回路和欧拉通路的情况所有房间都是偶数个门并且起始房间就是0所以可以回到0存在欧拉回路有两个房间的门是奇数个其余都是偶数个这种情况下要求出发房间和0房间的门是奇数个并且其实房间不能是0因为不存在0到0的欧拉回路但是存在别的房间到0的欧拉通路。 1 //POJ 13002 #include stdio.h3 #include string4 #include iostream5 #include string.h6 7 using namespace std ;8 9 int M,N,door[20] ;
10 string sh ;
11 char sh1[789] ;
12 int main()
13 {
14 while(cin sh)
15 {
16 if(sh ENDOFINPUT)
17 break ;
18 cin M N ;
19 getchar() ;
20 int cnt 0 ;
21 memset(door,0,sizeof(door)) ;
22 for(int i 0 ; i N ; i)
23 {
24 gets(sh1) ;
25 int len strlen(sh1) ;
26 for(int j 0 ; j len ; j)
27 {
28 if(sh1[j] ! )
29 {
30 int d sh1[j]-0 ;
31 cnt ;
32 door[i] ;
33 door[d] ;
34 }
35 }
36 }
37 cin sh ;
38 int odd 0 ,even 0 ;
39 for(int i 0 ; i N ; i)
40 {
41 if(door[i] % 2) odd ;
42 else even ;
43 }
44 if(odd 0 M 0)
45 cout YES cnt endl ;
46 else if(odd 2 M ! 0)
47 cout YES cnt endl ;
48 else coutNOendl ;
49 }
50 return 0 ;
51 } View Code 转载于:https://www.cnblogs.com/luyingfeng/p/3877442.html
