慕容琳的后花园
慕容琳的后花园
洛谷#P1444#虫洞

虫洞

农夫约翰爱好在周末进行高能物理实验的结果却适得其反,导致N个虫洞在农场上(2<=N<=12,n是偶数),每个在农场二维地图的一个不同点。
根据他的计算,约翰知道他的虫洞将形成 N/2 连接配对。例如,如果A和B的虫洞连接成一对,进入虫洞A的任何对象体将从虫洞B出去,朝着同一个方向,而且进入虫洞B的任何对象将同样从虫洞A出去,朝着相同的方向前进。这可能发生相当令人不快的后果。
例如,假设有两个成对的虫洞A(1,1) 和 B(3,1),贝茜从(2,1)开始朝着 +x 方向(右)的位置移动。贝茜将进入虫洞 B(在(3,1)),从A出去(在(1,1)),然后再次进入B,困在一个无限循环中!

| . . . .
| A > B .      贝茜会穿过B,A,
+ . . . .      然后再次穿过B

农夫约翰知道他的农场里每个虫洞的确切位置。他知道贝茜总是向 +x 方向走进来,虽然他不记得贝茜的当前位置。请帮助农夫约翰计算不同的虫洞配对(情况),使贝茜可能被困在一个无限循环中,如果她从不幸的位置开始。

解法

枚举各种匹配方案,然后去深搜判环,有两种走法
一种是从左边进去一个虫洞,会从匹配的虫洞出来
还有一种是从一个虫洞出来,会从它右边的第一个虫洞的匹配的虫洞出来
枚举从任意一个虫洞进去,然后重复执行第二种,看出来的虫洞是否重复就可以判断有无环了

ac代码

#include<bits/stdc++.h>
using namespace std;
struct node{int x,y;}p[20];
bool cmp(node a,node b){return a.y==b.y?a.x<b.x:a.y<b.y;}
int n,ans=0,to[20],e[20],vis[20],flg;
//to表示直接向右走能到达的点
//e表示对应点
bool check(int x)
{
    memset(vis,0,sizeof(vis));
    while(to[x])
    {
        if(vis[x])return 1;
        vis[x]=1,x=e[to[x]];
        //去到当前节点能走到的下一个节点的对应点
    }
    return 0;
}
void dfs(int k)
{
    if(k>n){for(int i=1;i<=n;i++)if(check(i)){ans++;break;}}
    //如果匹配完成,检验有无环
    else if(e[k])dfs(k+1);
    //如果当前点被匹配过,无需匹配
    else for(int i=k+1;i<=n;i++)if(!e[i])e[i]=k,e[k]=i,dfs(k+1),e[i]=e[k]=0;
    //匹配后进入下一个点
}
int main()
{
    cin >> n;
    for(int i=1;i<=n;i++)cin >> p[i].x >> p[i].y;
    sort(p+1,p+1+n,cmp);
    for(int i=1;i<=n-1;i++)if(p[i].y==p[i+1].y)to[i]=i+1;
    dfs(1),cout << ans << endl;
    return 0;
}
赞赏
首页      洛谷      洛谷#P1444#虫洞
https://secure.gravatar.com/avatar/8cbc0c58deea66b18e9a96cd4bdd6eea?s=256&d=monsterid&r=g

慕容琳

文章作者

发表评论

textsms
account_circle
email

慕容琳的后花园

洛谷#P1444#虫洞
虫洞 农夫约翰爱好在周末进行高能物理实验的结果却适得其反,导致N个虫洞在农场上(2<=N<=12,n是偶数),每个在农场二维地图的一个不同点。 根据他的计算,约翰知道他的虫洞将形…
扫描二维码继续阅读
2019-05-06
功能