CF11D

Aryper · 2021-11-11 19:56:33 · 个人记录

A Simple Task

状压 DP。

定义状态比较有技巧，f(i,j) 表示点集为 i，以点集中编号最小的点为起点，j 为终点的路径的条数。然后环的数量就是所有 j 为 i 中最小点的 f(i,j) 之和。但是我们为了方便去重，不再去统计环的数量（否则似乎会把环套环也统计上），直接统计进答案即可。

于是乎，我们枚举每个状态，再枚举它可到达的终点有哪些，再枚举新的点看这种路径是否能扩展。然后新的点需要是终点，所以不能为编号最小的点。如果说可以形成环，自然统计进入答案，否则，我们利用此更新状态。

时间复杂度 O(n^22^n)。

这里去重不多做解释，即 ans\leftarrow \dfrac{ans-m}{2}。即减去自环，然后去掉方向相反的环。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define ll long long
using namespace std;

const ll N=19,I=1<<N;

ll n,m,u,v,ans;

ll f[I+5][N+5];

bool edge[N+5][N+5];

inline ll read() {
    ll ret=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-f;ch=getchar();}
    while(ch>='0'&&ch<='9') {ret=(ret<<3)+(ret<<1)+ch-'0';ch=getchar();}
    return ret*f;
}

void write(ll x) {
    static char buf[22];static ll len=-1;
    if(x>=0) {
        do{buf[++len]=x%10+48;x/=10;}while(x);
    }
    else {
        putchar('-');
        do{buf[++len]=-(x%10)+48;x/=10;}while(x);
    }
    while(len>=0) putchar(buf[len--]);
}

int main() {

    n=read();m=read();

    for(ll i=1;i<=m;i++) {
        u=read();v=read();
        edge[u][v]=edge[v][u]=1;
    }

    for(ll i=1;i<=n;i++) {
        f[1<<(i-1)][i]=1;
    }

    for(ll i=0;i<(1<<n);i++) {
        for(ll j=1;j<=n;j++) {
            if(!f[i][j]) continue;
            for(ll k=1;k<=n;k++) {
                if(!edge[j][k]) continue;
                if((1<<(k-1))<(i&-i)) continue;
                if((1<<(k-1))&i) {
                    if((1<<(k-1))==(i&-i)) {
                        ans+=f[i][j];
                    }
                }
                else {
                    f[i|(1<<(k-1))][k]+=f[i][j];
                }
            }
        }
    }

    write((ans-m)/2);

    return 0;
}