usaco wormhole（看了官方视频题解）

本文主要是介绍usaco wormhole（看了官方视频题解），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

看了视频看懂了但是递归那块求所有匹配可能我真的写不出来，而且经常弄混。

/*
ID:jinbo wu
LANG:C++
TASK:wormhole
*/
#include<bits/stdc++.h>
using namespace std;
int x[13];
int y[13];
int partner[13];
int next_on_right[13];
int n;
bool circle()
{for(int i=1;i<=n;i++)//遍历所有起点{int pos=i;for(int j=1;j<=n;j++)pos=next_on_right[partner[pos]];//走遍所有点后如果位置不为0即还在虫洞中既有环if(pos!=0)return 1;}return 0;
}
int solve()//递归求所有可能匹配
{int i,total=0;for(i=1;i<=n;i++)if(partner[i]==0) break;if(i>n)//找到一个完整匹配{if(circle()) return 1;//判断能不能构成环else return 0;}for(int j=i+1;j<=n;j++){if(partner[j]==0){partner[i]=j;partner[j]=i;total+=solve();partner[i]=partner[j]=0;}}return total; 
}
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",&x[i],&y[i]);for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){if(x[i]<x[j]&&y[i]==y[j]){if(next_on_right[i]==0||x[j]-x[i]<x[next_on_right[i]]-x[i])next_on_right[i]=j;}}printf("%d\n",solve());
}

这篇关于usaco wormhole（看了官方视频题解）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---