CF11D A Simple Task

Luogu

Codeforces

题意

求简单无向图的环数。

算法

可以枚举所有环,然后判断是否存在。但是这样显然会TLE。

发现$n$很小,所以考虑状压DP。

设$f[S][i]$表示$S$中最小的点到$i$的路径数。

考虑怎么转移。枚举$i$能到达的点$j$。如果$j$是$S$中最小的点,ans+=f[S][i];否则,f[S|(1<<(v-1)][j]+=f[S][i]

然后这样会算一堆双向边,每个环还会算两次。所以答案实际上是$(ans-m)/2$。

代码

#include <bits/stdc++.h>
#define re register
#define lowbit(x) ((x)&(-(x)))
typedef int mainint;
#define int long long
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=(X<<3)+(X<<1)+c-'0',c=getchar();
    return X*w;
}

struct Edge { int v,nxt; } e[400];
int head[20],cnt=0;

inline void addEdge(int u,int v) {
    e[++cnt].v=v;
    e[cnt].nxt=head[u];
    head[u]=cnt;
}

int f[1<<19][20]; //f[S][i]表示S中最小的点到i的路径数 

mainint main() {
    int n=read(),m=read();
    for (re int i=1,u,v;i<=m;i++) {
        u=read(),v=read();
        addEdge(u,v);
        addEdge(v,u);
    }
    for (re int i=1;i<=n;i++) f[1<<(i-1)][i]=1; //边界
    int ans=0;
    for (re int S=0;S<(1<<n);S++) {
        for (re int i=1;i<=n;i++) {
            if (!f[S][i]) continue;
            for (re int k=head[i];k;k=e[k].nxt) {
                int j=e[k].v;
                int U=lowbit(S),V=1<<(j-1);
                if (U>V) continue;
                if (V&S) {
                    if (U==V) ans+=f[S][i];
                }
                else f[S|V][j]+=f[S][i];
            }
        }
    }
    printf("%lld\n",(ans-m)/2);
    return 0;
}
最后修改:2019 年 09 月 24 日 01 : 27 PM

发表评论