首页 > 代码库 > POJ 1300 最基础的欧拉回路问题

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

2024-07-19 23:14:47   219人阅读

题目大意：

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

 

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

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

 

这里只有两种情况能成功

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

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

 

代码：

 1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 using namespace std; 5 int door[22]; 6 int readLine(char *s){ 7     int L; 8     for(L=0;(s[L]=getchar())!=‘\n‘&&s[L]!=EOF;L++); 9     s[L]=0;10     return L;11 }12 int main()13 {14     char buf[128];15     int m,n;16     while(readLine(buf)){17         if(buf[0]==‘S‘){18             sscanf(buf,"%*s %d %d",&m,&n);19             memset(door,0,sizeof(door));20 21             int numOfDoor=0;//记录所有门的数量，为了最后结果输出总共关上的门的数目22             for(int i=0;i<n;i++){23                 readLine(buf);24                 int k=0,j;//读取数据在字符串中的指针位置25                 while(sscanf(buf+k,"%d",&j)==1){26                     door[i]++,door[j]++;27                     numOfDoor++;28                     while(buf[k]&&buf[k]==‘ ‘)k++;29                     while(buf[k]&&buf[k]!=‘ ‘)k++;30                 }31             }32             readLine(buf);//读入END33             int odd=0,even=0;34             for(int i=0;i<n;i++){35                 if(door[i]%2!=0)odd++;36                 else even++;37             }38             if(odd==0&&m==0) printf("YES %d\n",numOfDoor);39             else if(odd==2&&door[m]%2==1&&door[0]%2==1&&m!=0) printf("YES %d\n",numOfDoor);40             else puts("NO");41         }42         else if(!strcmp(buf,"ENDOFINPUT")) break;43     }44     return 0;45 }

 

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


联系
我们