[USACO1.3]虫洞wormhole 2021-11-25 大意 给定一些点,在横向穿过这些点时将会被传送回纵坐标相同的 y y y轴上,问有多少种情况会使得永远向右爬的虫子陷入死循环 思路 【[USACO1.3]虫洞wormhole】首先因为只会向右爬,所以我们只需将同一行上的点间连边,然后 d f s dfs dfs暴力找匹配,之后判环即可 代码 /* ID:hzbismy1 LANG:C++ TASK:wormhole */ #include #include #include #define x second #define y first using namespace std; int n,to[20],pre[20],ans; bool vis[20]; pairp[20]; inline bool check(register int k)//判环 { while(to[k]) { if(vis[k]) return true; vis[k]=true; k=pre[to[k]]; } return false; } inline void dfs(register int dep)//暴力找匹配 { if(dep>n) { for(register int i=1; i<=n; i++) { fill(vis+1,vis+1+n,0); if(check(i)){ans++; return; } } return; } if(pre[dep]) dfs(dep+1); else { for(register int i=dep+1; i<=n; i++) if(!pre[i]) { pre[i]=dep; pre[dep]=i; dfs(dep+1); pre[i]=0; pre[dep]=0; } } } signed main() { freopen("wormhole.in","r",stdin); freopen("wormhole.out","w",stdout); scanf("%d",&n); for(register int i=1; i<=n; i++) scanf("%d%d",&p[i].x,&p[i].y); sort(p+1,p+1+n); for(register int i=1; i 推荐阅读 大神童全自动洗衣机排水阀在哪里 全自动洗衣机排水阀在哪里 电脑3d建模软件推荐 goosipredis 橡木和pvc洗脸盆哪种材质好 橡木和pvc洗脸盆哪种材质好呢 葡萄干和桃子能一起吃吗 提新车验车真的那么麻烦吗? 验车宝典 全球|三星手机连续五年全球销量第一,你用三星手机吗? 星夜 感应草的功效与作用 金枪鱼家用冰箱可以保存几天 金枪鱼可以家用冰箱保存吗 吃芒果全身过敏怎么办 金字旁加兆念什么 金字旁加兆念什么字 腐竹牛腩的做法大全窍门 腐竹牛腩的做法大全 五本修仙文推荐 女主在仙魔妖三界跑酷,把虐文剧本改成爽文人生 有什么恐怕小说推荐吗?在哪可以看? 挂出个大侠礼包码大全,官方礼包兑换码汇总 茶叶种植条件有哪些? 居家隔离心情不好怎么办 小孩性格软弱怎么教育 为什么现在很多女生踩鞋跟 洛谷 P2850 [USACO06DEC]虫洞Wormholes 虫洞 usaco|BZOJ 1715: [Usaco2006 Dec]Wormholes 虫洞