Loj#2290.「THUWC 2017」随机二分图 | wzf2000's blog

Loj#2290.「THUWC 2017」随机二分图

Loj#2290.「THUWC 2017」随机二分图 题解

题意:

  • 略。

题解:

  • 考虑这样的一种 $\rm dp$:
    • 用 $dp[S][T]$ 表示左边匹配了点集为 $S$ 的点,右边匹配了点集为 $T$ 的点。
    • 对于每个有意义的状态转移。
  • 这个 $\rm dp$ 有用的状态数其实是几百万左右,所以时间上可以接受。
  • 然而这只能解决 $t=0$ 的情况。
  • 考虑 $t=1$,两条边同时匹配的概率计算了是 $\frac{1}{4}$,然而实际上同时出现的概率是 $\frac{1}{2}$,所以加一个两个同时匹配的转移。
  • 同理 $t=2$,加一个负的同时匹配的转移。
  • 时间复杂度玄学。

代码:

#include <bits/stdc++.h>
#define gc getchar()
using namespace std;
typedef long long ll;
const int mod=1000000007;
const int N=10000009;
const int M=239;
int n,m,cnt,number,nxt[16][16],g[16][16],first[16];
struct edge
{
    int to,next;
    void add(int x,int y)
    {
        to=y,next=first[x],first[x]=number;
    }
}e[M];
map<int,int> f[1<<16];
void add(int &x,int y)
{
    x=(x+y>=mod?x+y-mod:x+y);
}
int get(int x)
{
    int ret=0;
    while (x>>ret&1) ret++;
    return ret;
}
int read()
{
    int x=1;
    char ch;
    while (ch=gc,ch<'0'||ch>'9') if (ch=='-') x=-1;
    int s=ch-'0';
    while (ch=gc,ch>='0'&&ch<='9') s=s*10+ch-'0';
    return s*x;
}
int main()
{
    n=read(),m=read();
    for (int i=1;i<=m;i++)
    {
        int op=read(),x=read()-1,y=read()-1;
        e[++number].add(x,y);
        if (op)
        {
            int xx=read()-1,yy=read()-1;
            e[++number].add(xx,yy);
            if (x==xx||y==yy) continue;
            if (x>xx) swap(x,xx),swap(y,yy);
            nxt[x][y]=xx*n+yy,g[x][y]=op;
        }
    }
    f[0][0]=1;
    for (int i=0;i<(1<<n);i++)
    {
        int x=get(i);
        if (x==n) continue;
        for (auto now:f[i])
        {
            for (int k=first[x];k;k=e[k].next)
            {
                int y=e[k].to;
                if (now.first>>y&1) continue;
                add(f[i|1<<x][now.first|1<<y],now.second);
                if (g[x][y])
                {
                    int xx=nxt[x][y]/n,yy=nxt[x][y]%n;
                    if (i>>xx&1||now.first>>yy&1) continue;
                    add(f[i|1<<x|1<<xx][now.first|1<<y|1<<yy],g[x][y]==1?now.second:mod-now.second);
                }
            }
        }
    }
    printf("%d\n",f[(1<<n)-1][(1<<n)-1]);
    return 0;
}