首页 > 代码库 > POJ 1300 Door Man（欧拉回路的判定）

POJ 1300 Door Man（欧拉回路的判定）

2024-07-14 20:06:47   220人阅读

题目链接

题意 ： 庄园有很多房间，编号从0到n-1,能否找到一条路径经过所有开着的门，并且使得通过门之后就把门关上，关上的再也不打开，最后能回到编号为0的房间。

思路 ： 这就是一个赤裸裸的判断欧拉通路的问题了，但实际上，就只有两种情况能够输出YES，以房间为顶点，连接房间之间的门为边构造图，这两种情况分别是存在欧拉回路和欧拉通路的情况：所有房间都是偶数个门并且起始房间就是0，所以可以回到0，存在欧拉回路；有两个房间的门是奇数个，其余都是偶数个，这种情况下，要求出发房间和0房间的门是奇数个，并且其实房间不能是0，因为不存在0到0的欧拉回路，但是存在别的房间到0的欧拉通路。

 1 //POJ 1300 2 #include <stdio.h> 3 #include <string> 4 #include <iostream> 5 #include <string.h> 6  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 cout<<"NO"<<endl ;49     }50     return 0 ;51 }
View Code

 


联系
我们