POJ 1300 Door Man - c++编程基础

TOP

POJ 1300 Door Man

2015-07-24 05:41:50 来源: 作者: 【大中小】浏览:5次

判断是否欧拉回路。

很蛋疼的一道题，加上DFS判所有点是否连通就无限WA。（并查集也可判）

直接定理就AC了。都不知道所有点是不是在一个连通块里面。

然后他们说：Your master is a particularly absent-minded lout and continually leaves doors open throughout a particular floor of the house.

这句话就表明了连通……问题是，中间关几个门让他无法通过，前后都有门没关怎么办……

比如：

START 0 5
1 1

4 4

END

这怎么关门…… POJ AC的程序完全过不了这组数据啊。

好吧，贴上POJ AC程序，再贴上→_→ 真正意义上正确的程序。

AC 代码：

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #include
         #include
         
           #include
          
            #include
           
             #include
            
              #include
             
               #define INF 0x7fffffff #define eps 1e-6 using namespace std; int n,m; int in[21],out[21]; int door; bool Euler() { int s[21],cot=0; for(int i=0; i
              
               2||cot==1)return 0; if(cot==0&&m==0)return 1; if(s[0]==0&&s[1]==m||s[0]==m&&s[1]==0)return 1; return 0; } int main() { char str[100]; while(scanf("%s",str)!=EOF) { if(strcmp(str,"ENDOFINPUT")==0)return 0; scanf("%d%d",&m,&n); gets(str); door=0; memset(in,0,sizeof(in)); memset(out,0,sizeof(out)); for(int i=0; i
               
                ='0'&&str[j]<='9') c=c*10+str[j]-'0'; else { if(c==0)continue; door++; in[c]++,out[i]++; out[c]++,in[i]++; c=0; } } } while(gets(str),strcmp(str,"END")); bool flag=1; flag=Euler(); if(flag)printf("YES %d\n",door); else puts("NO"); } }

“错误”代码：

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #include
         #include
         
           #include
          
            #include
           
             #include
            
              #include
             
               #define INF 0x7fffffff #define eps 1e-6 using namespace std; int g[21][21]; int n,m; int in[21],out[21]; int ans; bool vis[21]; bool Euler() { for(int i=0; i
              
               %d\n",i,j); dfs(j); } int main() { char str[100]; while(scanf("%s",str)!=EOF) { if(strcmp(str,"ENDOFINPUT")==0)return 0; scanf("%d%d",&m,&n); gets(str); memset(g,0,sizeof(g)); memset(in,0,sizeof(in)); memset(out,0,sizeof(out)); for(int i=0; i
               
                ='0'&&str[j]<='9') c=c*10+str[j]-'0'; else { if(c==0)continue; g[i][c]++,in[c]++,out[i]++; g[c][i]++,out[c]++,in[i]++; c=0; } } } while(gets(str),strcmp(str,"END")); bool flag=1; flag=Euler(); memset(vis,0,sizeof(vis)); ans=0; dfs(m); for(int i=0; i


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：uva 10555 - Dead Fraction)(数论)	下一篇：C++中str1::function和bind

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: