Wormholes
2017.06.01
###题解###
深搜出所有可能的配对,再进行检验。检验方法为任意点开始经过N个点后还在图内即为一种情况。可以用一个right数组记录一个虫洞向右遇到的第一个虫洞以方便计算。
###代码###
/*
ID: xhzdcyy1
PROB: wormhole
LANG: C++
*/
#include <iostream>
#include <fstream>
#include <string>
#include <algorithm>
#define cin fin
#define cout fout
using namespace std;
ofstream fout ("wormhole.out");
ifstream fin ("wormhole.in");
const int MAX=15;
int n;
int x[MAX],y[MAX],right1[MAX]={0},p[MAX]={0};
int res=0;
bool loop(int s){
for(int i=1;i<=n;i++){
if(right1[s]==0) return 0;
s=right1[s];
s=p[s];
}
return 1;
}
void dfs(int nn){
if(nn==n){
for(int i=1;i<=n;i++){
if(loop(i)){
++res;
break;
}
}
return;
}
if(p[nn]==0){
for(int i=nn+1;i<=n;i++){
if(p[i]==0){
p[i]=nn;
p[nn]=i;
dfs(nn+1);
p[i]=0;
p[nn]=0;
}
}
}
else{
dfs(nn+1);
}
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++){
cin>>x[i]>>y[i];
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(y[i]==y[j]&&x[j]>x[i]&&(right1[i]==0||x[j]<x[right1[i]])){
right1[i]=j;
}
}
}
dfs(1);
cout<<res<<endl;
return 0;
}