P1444 [USACO1.3] 虫洞 wormhole

题目描述

Farmer John 周末进行高能物理实验的结果却适得其反，导致 $n$ 个虫洞出现在农场上，农场是一个二维平面，没有两个虫洞处于同一位置。

根据他的计算，FJ 知道他的虫洞两两配对，形成 $\frac{n}{2}$ 对配对。例如，如果 $A$ 和 $B$ 的虫洞连接成一对，进入虫洞 $A$ 的任何物体将从虫洞 $B$ 出去，方向不变；反之亦然。

然而这可能发生相当令人不快的后果。例如，假设有两个成对的虫洞 $A(1,1)$ 和 $B(3,1)$，Bessie 从 $(2,1)$ 开始朝着 $x$ 正方向移动。Bessie 将进入虫洞 $B(3,1)$，从 $A(1,1)$ 出去，然后再次进入 $B$，困在一个无限循环中！

FJ 知道他的农场里每个虫洞的确切位置。他知道 Bessie 总是向 $x$ 正方向走进来，虽然他不记得贝茜的当前位置。

请帮助 FJ 计算有多少种虫洞配对方案，使得存在一个位置，使得 Bessie 从该位置出发，会被困在一个无限循环中。

输入格式

第一行一个正整数 $n$，表示虫洞数量。

接下来 $n$ 行，每行两个整数 $x,y$，表示一个虫洞的坐标。

输出格式

输出一行一个整数表示答案。

输入输出样例 #1

输入 #1

4
0 0
1 0
1 1
0 1

输出 #1

2

说明/提示

数据范围

对于 $100\%$ 的数据，$2\le n\le 12$，$0\le x,y\le 10^9$。
保证 $n$ 为偶数。

样例解释

将虫洞编号为 $1\sim 4$，然后通过将 $1,2$ 和 $3,4$ 匹配，如果 Bessie 从 $(0,0)$ 到 $(1,0)$ 之间的任意位置出发，她会陷入无限循环中。

相似的，在相同的起始点，如果配对是 $1,3$ 和 $2,4$，贝茜也会陷入循环。（如果贝西从 $3$ 进去，$1$ 出来，她会走向 $2$ ，然后被传送到 $4$，最后又回到 $3$）

仅有 $1,4$ 和 $2,3$ 的配对允许贝茜从任何二维平面上的点向 $x$ 正方向走，而不出现无限循环。

题面翻译摘自 NOCOW

C++实现

#include<bits/stdc++.h>
using namespace std;
const int N=20;
struct Pos {
int x,y;
} p[N];
bool cmp(const Pos &a, const Pos &b) {
return a.y<b.y || (a.yb.y && a.x<b.x);
}
int n;
int to[N];
bool tag[N];
int con[N];
bool cycle(int x) {
while(to[x]) {
if(tag[x]) return 1;
tag[x]=1;
x=con[to[x]];
}
return 0;
}
int ans=0;
void dfs1(int k) {
if(k>n) {
bool ok=0;
for(int i=1;i<=n && !ok;i++)
memset(tag,0,sizeof(tag)), ok|=cycle(i);
ans+=ok;
return;
}
if(con[k]) dfs1(k+1);
else {
for(int i=k+1;i<=n;i++)
if(!con[i]) {
con[i]=k, con[k]=i;
dfs1(k+1);
con[i]=con[k]=0;
}
}
}
int main() {
scanf(“%d”,&n);
for(int i=1;i<=n;i++) scanf(“%d%d”,&p[i].x,&p[i].y);
sort(p+1,p+1+n,cmp);
for(int i=1;i<=n-1;i++)
if(p[i].yp[i+1].y) to[i]=i+1;
dfs1(1);
printf(“%d\n”,ans);
return 0;
}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容