Door man

题意：给你n个房间，房间之间有一些门，房间是按0~~n-进行编号的。然后给出一些房间的之间门，n行，每行的数字表示该们与其它们之间是否有门，而且只表示出比他大的房间号。然后给你一个起点，问你从起点出发，然后经过所有的房间回到0点，房间之间可能有多道门。

题解：题目描述的可能不是很清楚，题目是要求一条欧拉回路。源点是0点，可以从起点到达源点之后，看看能否经过每个房间回到0点。

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 #include<algorithm>
 5 using namespace std;
 6 int readLine(char *s){
 7     int L;
 8     for(L=0;(s[L]=getchar())!='
'&&s[L]!=EOF;L++);
 9     s[L]=0;
10     return L;
11 }//取出每一行，并且返回串的长度（包括空格）； 
12 int main(){
13     char buf[128];
14     int i,j,m,n;int door[20];
15     while(readLine(buf)){
16         if(buf[0]=='S'){
17             sscanf(buf,"%*s%d%d",&m,&n);//读取起点和房间的个数 *%s包第一个字符串吃掉了 
18             for( i=0;i<n;i++)
19               door[i]=0;//初始化 
20               int doors=0;//记录门的个数 
21               for(i=0;i<n;i++){
22                   readLine(buf);//读取一行 
23                   int k=0;//表示从哪一位开始读取 
24                   while(sscanf(buf+k,"%d",&j)==1){
25                       doors++;
26                       door[i]++;
27                       door[j]++;
28                       while(buf[k]&&buf[k]==' ')k++;//表示把k移动两位，来读取下一个数 
29                       while(buf[k]&&buf[k]!=' ')k++;// 
30                   }
31               }
32               readLine(buf);//读取END 
33               int even=0;//记录偶度点的个数 
34               int odd=0;//记录奇度点的个数 
35              for( i=0;i<n;i++){
36                   if(door[i]%2==0)even++;
37                   else
38                   odd++;
39              }
40           if(odd==0&&m==0)//如果起点是0并且没有奇度点直接输出 
41               printf("YES %d
",doors);
42           else if(odd==2&&door[m]%2==1&&m!=0&&door[0]%2==1)//如果有两个，分别是起点和0，并且起点不是0 
43             printf("YES %d
",doors);
44             else
45             printf("NO
");           
46               
47         }
48        if(!strcmp(buf,"ENDOFINPUT"))break;
49     }
50   return 0;    
51 }

View Code