完美匹配（matching）

71 阅读 0 评论 47 点赞

我是靠谱客的博主瘦瘦冬天，最近开发中收集的这篇文章主要介绍完美匹配（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
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("%dn",ask((1<<n)-1));
return 0;
}