wormhole解题报告 —— icedream61 博客园（转载请注明出处）
------------------------------------------------------------------------------------------------------------------------------------------------
【题目】
一个人在二维坐标系上走，方向永远是+x。此坐标系中有N个虫洞（N是偶数）。
虫洞这东西，一旦两个配成一对，便可以形成“传送门”的效果，进入一个就会被传送到另一个的位置且方向不变。
这时，有趣的事情出现了！假设有一对虫洞(1,1)和(3,1)，此人从(2,1)开始朝着+x方向（右）移动，将进入虫洞(3,1)，传送到(1,1)，然后再次走入(3,1)，困在一个无限循环中！
请问：你有多少种“机智的”将虫洞两两配对的方案，使这个人有可能在坐标系中陷入死循环走不出去？
【数据范围】
2<=N<=12
【输入格式】
第一行给出N，后面N行依次给出N个虫洞的坐标。
【输出格式】
一个整数，表示“机智的”配对方案数。
【输入样例】
4
0 0
1 0
1 1
0 1
【输出样例】
2
------------------------------------------------------------------------------------------------------------------------------------------------
【分析】
1、首先，你要找到一种枚举配对方案的方法（排列组合知识），只要保证不重复不遗漏就可以。这里仅给出我想到的枚举方法。
N个虫洞保持原顺序不变，我们要配出N/2对来。
第一对，我们定为1号虫洞和任意另一个虫洞，共N-1种；
第二对，我们定为剩下的虫洞中编号最小的虫洞和任意另一个虫洞，共N-3种；
第三对，同理，共N-5种……
以此类推，直至配出N/2种。我们来数一数，配对总方案数Sum=(N-1)×(N-3)×...×3*1，取N最大值12，则有Sum最大值10395，并不大。
2、然后，我们只需要验证某一种方法是否正确，即看看此种方案是否可以让这个倒霉蛋陷入死循环。显然，想让他陷入死循环肯定要他从某个有虫洞的行出发才行。那么，不妨让他在开始就从某个虫洞出来，或者刚刚进入某个虫洞。这时我们开始监控，看看这家伙怎么走的：
开始，他从a洞出来，必然会走到与a洞同一行（y值相同）且在a洞右边（x值更大）的所有虫洞中最靠左边的那个（x值最小），记为b洞。
而后，他走入b洞，传送到c洞，再重复上述过程……
那么问题来了，这样走下去，如何判断他是否走入了死循环呢？我给出的方法是：当他走入某个之前走入过的洞，或者从某个之前走出的洞走出时，便可认为他陷入了死循环。可见，我们对每种方案的模拟中，最多把所有虫洞走过一遍，时间也就是O(N)而已，很快。
3、如此一来，我们用时10395×12≈100000，完全可以接受，此题搞定。
------------------------------------------------------------------------------------------------------------------------------------------------
【总结】
这道题的确很精巧，看似简单的模型下，有很多的细节问题，对于新手是个不错的锻炼！
当然，对于我这种长时间没编程的准新手，也是相当大的锻炼……下面是我的调试全过程。。。
有机会，可以考虑把这道题再写一遍，是个不错的题目！
------------------------------------------------------------------------------------------------------------------------------------------------
【调试全过程】
第一次过了2个点，第三个点WA。
明明很显然可以循环的方案，却走不通。调试发现，奶牛是+x走，所以应该是相对当前位置y相等x更大的洞可以跳，我把x和y弄反了。
第二次过了3个点，第四个点超时……
USACO是文件输入输出，所以提交代码时，调试的屏幕输出可以不删，不影响对错。但是，我的屏幕输出过长，太占时间了……
第三次和第二次情况一样，也是超时……
1.屏幕输出删了，但时间仍是很长，应该是算法出了问题。调试发现，我只想到了可以从a洞出发，最终回到a洞；并未考虑到从a洞出发到b洞，然后若干次回到b洞，形成循环。因此，我不能只存开始的那一个洞，而应当把所有经过的洞都存下来，出现循环就说明此配对方案可行。
2.我发现屏幕输出很少，不可能向我之前推测的那样超时，于是我又加回去了。
第四次过了3个点，第四个点WA。
若同一行有超过2个虫洞，则中间的虫洞会截断两边虫洞的交流，导致从左边走不到右边。即，若同行按照x升序有a、b、c三个洞，则从a洞开始走只能走到b洞，无法走到c洞。
第五次第一个点就WA了。。
1.这次告诫我，交之前最好要测下样例……
2.这次检查代码时发现，开始写复杂了，奶牛走的过程中，根本不需要记录位置，记录虫洞的编号就好了。
3.解决第四次提交的问题时，代码中有个循环取消了，但其内部的一个break没有取消，于是这个break就退出了一个外层循环，导致WA。
第六次和第四次一样，输出也一样。。
1.这次再次告诫我，交之前要测下样例……
2.我不的不承认，这题的确很精巧！对于所谓“陷入循环”的判断条件必须很精确才行，有一点不清晰都会WA。
3.问题是这样的（这是第4组数据），比如一行我依次有b、c、f、a、d五个洞，另一行有单独一个e洞，一共6个洞。我们这样连：(a,b)(c,e)(d,f)。当我们从a洞出发，会走到d跳到f，再走到a。注意！这时并未陷入循环！因为我们只是走到a，而非从a走出！此时，我们会跳到b，再走到c跳到e，而后再也找不到洞了。我之前对“陷入循环”的判断方式，是走到之前走到过的洞就算。应该改为：走入之前走入的洞，或者从之前走出过的洞走出。
4.另外还发现，我之前对于从任意洞出发应当走到哪个洞，记录的信息有误。准确地说，是生成的方式有误，单向链表不好维护，因此我决定我改用双向链表的方式。
第七次过了6个点，第七个点超时。
1.我先把数据考下来自己运行一遍试试，看看到底是哪儿超时。
2.正好借这个机会，我练习了下用宏来开关调试代码。
3.竟然真的是屏幕输出超时……
4.关掉，交上去，经过漫长的等待……USACO崩了……好像突然USACO变得很慢……上不去了。。等吃完中午饭再交吧-.-
5.网又好了……交上去，等了几秒……AC了！nice～！
------------------------------------------------------------------------------------------------------------------------------------------------
【代码】
/*
ID: icedrea1
PROB: wormhole
LANG: C++
*/ #include <iostream>
#include <fstream>
//#define test
using namespace std; struct Point { int x,y; };
struct Hole
{
Point site;
int to;
int l,r;
}; int N,Sum;
Hole H[+]; void print()
{
for(int i=;i<=N;++i)
{
cout<<"H["<<i<<"]\tsite=("<<H[i].site.x<<","<<H[i].site.y<<")\tto="<<H[i].to<<endl;
}
cout<<endl;
} bool check()
{
for(int i=;i<=N;++i)
{
// 以H[i].site为起点
#ifdef test
cout<<"i = "<<i<<endl;
#endif // test
int now;
bool p=true,mark[+][]={}; // mark[i][0]=true表示曾经从i点出来过，mark[i][1]=true则表示从i点进入过
now=i; mark[now][]=true;
while(p) // 刚开始 或 上次跳了
{
p=false;
#ifdef test
cout<<"\tnow = "<<now<<"\tr = "<<H[now].r<<"\t";
#endif // test
if(H[now].r)
{
int j=H[now].r; now=H[j].to;
// 从i走到j，再跳到H[j].to.site
#ifdef test
cout<<"\tthrougn ("<<j<<") now = "<<now<<endl;
#endif // test
if(mark[j][] || mark[now][])
{
#ifdef test
cout<<"\tcheck success"<<endl;
cout<<"--------------------------------------------------------------------"<<endl;
#endif // test
return true;
}
mark[j][]=mark[now][]=true;
p=true;
}
#ifdef test
else cout<<endl;
#endif // test
};
}
#ifdef test
cout<<"\tcheck fails"<<endl;
cout<<"--------------------------------------------------------------------"<<endl;
#endif // test
return false;
}
void match(int k)
{
if(k*>N)
{
#ifdef test
print();
#endif // test
Sum+=check(); return;
}
// 配第k对
int a,b;
for(int i=;i<=N;++i)
if(!H[i].to) { a=i; break; }
for(int i=a+;i<=N;++i)
if(!H[i].to)
{
b=i;
H[a].to=b; H[b].to=a; match(k+);
H[a].to=; // 这句可以省，因为进入下一次时，H[a].to一定会被重新赋值（未实测过）
// 但仍不建议省，毕竟不利于调试（调试时这里该空的时候却有上次的数据，会产生误导）
H[b].to=; // 这句不能省，否则到第二个b时，第一个b的to非空，就出错了
}
} int main()
{
ifstream in("wormhole.in");
ofstream out("wormhole.out"); in>>N;
for(int i=;i<=N;++i)
{
in>>H[i].site.x>>H[i].site.y;
for(int j=;j!=i;++j)
if(H[i].site.y==H[j].site.y)
{
int a=i,b=j,c;
if(a>b) swap(a,b); // 题目数据不可能a==b
while(H[a].site.x<H[H[b].l].site.x) b=H[b].l;
c=H[b].l;
H[a].r=b; H[b].l=a;
H[a].l=c; if(c) H[c].r=a;
}
} match(); out<<Sum<<endl; in.close();
out.close();
return ;
}