POJ 1300 最基础的欧拉回路问题

题目大意：

从0~n-1编号的房间，从一个起点开始最后到达0号房间，每经过一扇门就关上，问最后能否通过所有门且到达0号房间

我觉得这道题的输入输出格式是我第一次遇到，所以在sscanf上也看了很久

每一行对应当前门能到达的房间，下方如有重复不在输入，所以会有空行，这里的空行，和将字符串内的数字一个个代入需要好好斟酌

这里只有两种情况能成功

从 0号房间出发，经过一个欧拉回路到达0

从别的房间出发，一个欧拉通路到达0,2个端点的均为基度节点

代码：

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 using namespace std;

 int door[];

 int readLine(char *s){

     int L;

     for(L=;(s[L]=getchar())!='\n'&&s[L]!=EOF;L++);

     s[L]=;

     return L;

 }

 int main()

 {

     char buf[];

     int m,n;

     while(readLine(buf)){

         if(buf[]=='S'){

             sscanf(buf,"%*s %d %d",&m,&n);

             memset(door,,sizeof(door));

             int numOfDoor=;//记录所有门的数量，为了最后结果输出总共关上的门的数目

             for(int i=;i<n;i++){

                 readLine(buf);

                 int k=,j;//读取数据在字符串中的指针位置

                 while(sscanf(buf+k,"%d",&j)==){

                     door[i]++,door[j]++;

                     numOfDoor++;

                     while(buf[k]&&buf[k]==' ')k++;

                     while(buf[k]&&buf[k]!=' ')k++;

                 }

             }

             readLine(buf);//读入END

             int odd=,even=;

             for(int i=;i<n;i++){

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

                 else even++;

             }

             if(odd==&&m==) printf("YES %d\n",numOfDoor);

             else if(odd==&&door[m]%==&&door[]%==&&m!=) printf("YES %d\n",numOfDoor);

             else puts("NO");

         }

         else if(!strcmp(buf,"ENDOFINPUT")) break;

     }

     return ;

 }

巴特西

POJ 1300 最基础的欧拉回路问题

最新文章

热门文章