首页 > 代码库 > POJ 1300 最基础的欧拉回路问题
POJ 1300 最基础的欧拉回路问题
题目大意:
从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 最基础的欧拉回路问题
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。