POJ 1300 Door Man

判断是否欧拉回路。

很蛋疼的一道题,加上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; i2||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]

“错误”代码:

#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]

点击复制链接 与好友分享!回本站首页
您对本文章有什么意见或着疑问吗?请到论坛讨论您的关注和建议是我们前行的参考和动力
上一篇:C++运算符重载为友元函数学习笔记
下一篇:hdu3666 THE MATRIX PROBLEM --- 差分约束
相关文章

POJ3621最优比率生成环 01分数规划问题

poj 1928

poj 3728 tarjan+带权路径并查集

poj 3321

POJ 1664 放苹果 递推

poj 1631

poj模拟题总结(一)

POJ 1083

POJ 1952 BUY LOW, BUY LOWER

poj 1195

图文推荐

POJ 1300 Door Man
ZOJ 3640 Help Me
POJ 1300 Door Man
CF 518C(Anya and
POJ 1300 Door Man
hdu 1016 Prime R
UVA - 11987 - A

分类:默认分类 时间:2015-02-27 人气:2
本文关键词:
分享到:

相关文章

Copyright (C) quwantang.com, All Rights Reserved.

趣玩堂 版权所有 京ICP备15002868号

processed in 0.246 (s). 10 q(s)