这题可真是又让我找到了八数码的感觉。。。哈哈。
首先，第一次见题，没有思路，第二次看题，感觉是搜索，就这样写下来了。
这题我几乎是一个点一个点改对的（至于为什么是这样，后面给你看一个神奇的东西），让我发现了许多搜索上的问题。思路非常简
单：搜索出每一种可能的配对方式，然后从每一个点出发
一遍，模拟走的过程，如果到死循环里面就答案加一，那个模拟走的过程话说我敲的还是很爽的，这题难在对配对序列的搜索和配对状态重
复的剪枝上面。
记得配对序列的搜索我敲了5、6个版本，发现AC之后一个都没有用上，但是在这个过程中，你脑袋里面模拟那个搜索的过程的确是很爽
啊，确定了搜索序列的方法之后，就分别对每一个序列执行模拟走的操作，但是，这是一个严重的问题出现了，大量的重叠状态，导致所有
N = 12的数据严重超时，让人更加不理解的是，USACO上原题还有小于12的数呢，但是COGS上的数据好像全部都是12，坑了。但是，剪
枝的方法十分的妙，什么，单调。我给出一个不重复的序列作为说明：
当N等于6时，所有可能的序列如下：
12 34 56 | 12 35 46 | 12 36 45 |
13 24 56 | 13 25 46 | 13 26 45 |
14 23 56 | 14 25 36 | 14 26 35 |
15 23 46 | 15 24 36 | 15 26 34 |
16 24 35 | 16 23 45 | 16 25 34 |
我们可能清楚的发现，如果你的搜索顺序对的话，那么有一个神奇而又能让你通过测试的性质，就是这个序列无论什么样子，他的奇数位上
的数字都是单调递增的，正是因为这个东西，让我剪掉了数量非常大的无用状态。
至于怎么体现这句话，关键地方说完了，直接贴代码，自己看吧。。。有许多大神0.0几秒就过了，不能理解，我的0.6几秒，这效率，天
差地
别啊，，，自愧不如。。。。。
Code:
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <set>
#include <map>
using namespace std;
int N;
int Ans = 0;
bool vi[15];
bool a[15][15];
int que[15];
struct data{
int x,y;
}G[15];
int T[30];
int tot = 0;
void dfs(int,int,int);
bool cmp(data,data);
bool judge();
bool go(int,int);
void outandin();
int main(){
freopen("wormhole.in","r",stdin);
freopen("wormhole.out","w",stdout);
scanf("%d",&N);
for(int i = 1;i <= N;++ i){
scanf("%d%d",&G[i].x,&G[i].y);
T[++ tot] = G[i].x;
T[++ tot] = G[i].y;
}
outandin();
sort(G+1,G+N+1,cmp);
for(int i = 2;i <= N;++ i){
dfs(1,i,2);
}
printf("%d
",Ans);
return 0;
}
void dfs(int now,int next,int depth){
vi[now] = vi[next] = true;
que[depth] = now;que[depth+1] = next;
if(depth == N && N%2==0){
if(judge())
++ Ans;
return;
}
else if(depth == N-1 && N%2 == 1){
if(judge())
++ Ans;
return;
}
for(int i = 1;i <= N;++ i){
if(!vi[i] && i > now){//这括号里面很神奇的一句。。。i > now 剪枝的神器。。
for(int j = 1;j <= N;++ j){
if(!vi[j] && j != i && j > i){
dfs(i,j,depth+2);
vi[j] = false;
}
}
vi[i] = false;
}
}
vi[now] = vi[next] = false;
}
bool cmp(data a,data b){
if(a.x == b.x)
return a.y < b.y;
return a.x < b.x;
}
bool judge(){
for(int i = 2;i <= (N&1?N:N+1);++ i)
if(go(que[i],i))
return true;
return false;
}
bool go(int now,int pos){
bool v[15];
memset(v,false,sizeof v);
while(1){
if(v[now])
return true;
v[now] = true;
pos = ((pos&1) ? (pos-1):(pos+1));
bool flag = false;
for(int i = 1;i <= N;++ i){
int n = que[pos];
if(i != n && G[i].x > G[n].x && G[i].y == G[n].y){
for(int j = 2;j <= (N&1?N:N+1);++ j){
if(que[j] == i){
now = que[j];
pos = j;
flag = true;
break;
}
}
}
if(flag)
break;
}
if(!flag)
return false;
}
}
map <int,int> pos;
map <int,bool> fla;
void outandin(){
int no = 0;
for(int i = 1;i <= tot;++ i){
if(!fla[T[i]]){
fla[T[i]] = true;
pos[T[i]] = ++ no;
}
}
for(int i = 1;i <= N;++ i){
G[i].x = pos[G[i].x];
G[i].y = pos[G[i].y];
}
}
如果你不剪枝，但是时间又特别特别长的话（也就是没有超时这种东西），你的输出就要这样写：
if(N > 11)
printf("%d
",Ans/120);
else if(N > 9)
printf("%d
",Ans/24);
else if(N > 7)
printf("%d
",Ans/6);
else if(N > 5)
printf("%d
",Ans/2);
else
printf("%d
",Ans);
正是这个让我一个点一个点的过，也是这个让我发现了大量的重复状态，由那个/120你就知道重复状态有多么可怕了。。。。。
总之，模拟走的过程练码力，搜索的过程练搜索。。一道非常不错的题目。。。