完美匹配（matching）

　

完美匹配

完美匹配（matching）

题目描述

给定nn个点，mm条边的无向图G=(V,E)G=(V,E)，求出它的完美匹配数量对106+3106+3取模的值。

一个完美匹配可以用一个排列ϕ:V→Vϕ:V→V来表示，满足(v,ϕ(v))∈E(v,ϕ(v))∈E和ϕ(ϕ(v))=vϕ(ϕ(v))=v。

输入

输入第一行，包含两个整数n,mn,m，表示图GG的点数和边数。

接下来mm行，第i+1i+1行包含两个正整数ui,viui,vi，描述第ii条无向边。ui,viui,vi为该边两个端点的标号。

保证图中没有自环或重边。

输出

输出一个整数，表示图GG的完美匹配数量对106+3106+3取模的值。

样例输入

样例输入1
4 4
1 3
1 4
2 3
2 4

样例输出

样例输出1
2

提示

样例2,3

样例解释1

排列(3,4,1,2)(3,4,1,2)和(4,3,2,1)(4,3,2,1)满足条件。

数据范围

来源

南外NOIP2017模拟

---

solution

这题问你匹配的方案数

如果n是奇数，那么就是0

偶数的话，考虑状压

令f[S]表示当前匹配的点状态为S

每次挑出两个0来匹配

用哈希存状态，记忆化一下

效率O（可以过）

#include<cstdio>
#include<iOStream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
#define maxn 33
#define mod 1000003
#define p 1000007
using namespace std;
int n,m,head[p],t1,t2,tot=1;
int ma[maxn][maxn];
struct node{
    int v,nex,w;
}e[p*3];
void lj(int t1,int t2,int t3){
    tot++;e[tot].v=t2;e[tot].w=t3;e[tot].nex=head[t1];head[t1]=tot;
}
int f(int S,int T){
    for(int i=head[T];i;i=e[i].nex){
        if(e[i].v==S)return e[i].w;
    }
    return -1;
}
int ask(int S){
     
    if(!S)return 1;
    if(f(S,S%p+1)!=-1)return f(S,S%p+1);
    int fi=0,sum=0;
    for(;!(S&(1<<fi));fi++);
    for(int i=fi+1;i<=n;i++){
        if((S&(1<<i-1))&&ma[fi+1][i])sum+=ask(S^(1<<fi)^(1<<i-1));
        sum%=mod;
    }
    lj(S%p+1,S,sum);
    return sum;
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        scanf("%d%d",&t1,&t2);
        ma[t1][t2]=ma[t2][t1]=1;
    }
    printf("%d\n",ask((1<<n)-1));
    return 0;
}

相关阅读

首届“来电一下”共享充电宝设计大赛完美收官！100款定

历时两个月，来电科技与摸鱼塘共同发起的首届“来电一下”共享充电宝设计大赛完美收官！本次比赛共覆盖全国核心人群100万

一份完美的企业微信公众平台营销策划方案

微信已经成为人们生活的一部分，承载着各种“连接”需求与价值，越来越多的企业已经意识到这种连接的价值，也正尝试着通过微

电视盒子如何观看电视直播？当贝市场一招完美解决

很多朋友为了方便省钱在家中安装了电视盒子，而电视盒子却不能像智能电视那样直接观看电视直播，原因很简单，在电视盒子上需要安装观看

括号匹配（C++)

算法思想： 将输入的字符串遍历。 遇到左括号就压栈；遇到右括号，若栈不为空，就将栈顶的左括号取出，匹配返回一个bool值。 若直至遍历结

如何撰写一份完美的商业计划书，赢得投资人的青睐呢？

你是不是也想撰写一份投资人会喜欢的出色的商业计划书，但是又不知该如何开始？本文将会分享一些实用的商业计划书撰写技巧。一份出色