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

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

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

 //POJ 1300

 #include <stdio.h>

 #include <string>

 #include <iostream>

 #include <string.h>

 using namespace std ;

 int M,N,door[] ;

 string sh ;

 char sh1[] ;

 int main()

 {

     while(cin >> sh)

     {

         if(sh == "ENDOFINPUT")

             break ;

         cin >> M >> N ;

         getchar() ;

         int cnt =  ;

         memset(door,,sizeof(door)) ;

         for(int i =  ; i < N ; i++)

         {

             gets(sh1) ;

             int len = strlen(sh1) ;

             for(int j =  ; j < len ; j++)

             {

                 if(sh1[j] != ' ')

                 {

                     int d = sh1[j]-'' ;

                     cnt ++ ;

                     door[i] ++ ;

                     door[d] ++ ;

                 }

             }

         }

         cin >> sh ;

         int odd =  ,even =  ;

         for(int i =  ; i < N ; i++)

         {

             if(door[i] % ) odd ++ ;

             else even ++ ;

         }

         if(odd ==  && M == )

             cout<< "YES "<< cnt <<endl ;

         else if(odd ==  && M != )

             cout << "YES "<<cnt <<endl ;

         else cout<<"NO"<<endl ;

     }

     return  ;

 }

巴特西

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

最新文章

热门文章