写篇题解纪念一下这道神题。
这题思路比较繁杂，我就不说了，蓝书上有很详细的题解。
颓了大佬 @墨染空 的题解
\(H_i\) 表示\(i\)个点组成的连通图个数（可以顺手做做poj1737）
\(F_{i,j}\)表示\(i\)个点构成的包含\(j\)条割边的连通图个数
\(G_{i,j,k}\)表示\(i\)个点，\(j\)条割边，分成\(k\)个连通块 的无向图个数。
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
#define forg(i,x) for(int i=first[x];i;i=nxt[i])
#define forl(z,i,x) for(int i=z.first[x],y=z.to[i];i;i=z.nxt[i],y=z.to[i])
#define uu unsigned
#define fi first
#define se second
#define ran() ((unsigned)rand())
#define lam(z,k) [&](const z &a,const z &b){ return k; }
#define od(x) ((x)&1)
#define ev(x) (od(x)^1)
const int mod=1e9+7;
int n,m;
long long H[51],C[51][51],mi[51],F[51][51],G[51][51][51];
inline int Sum(int a,int b){
return (a+b>=mod)?a+b-mod:a+b;
}
inline int Sub(int a,int b){
return (a>=b)?a-b:a+mod-b;
}
inline int Mul(int a,int b){
return (long long)a*b%mod;
}
inline int por(int a,int b){
int res=1;
for(;b;b>>=1){
if(b&1)res=Mul(res,a);
a=Mul(a,a);
}
return res;
}
namespace poj1737 {
void solve(){
scanf("%d%d",&n,&m);
if(m>n-1)m=n-1;
for(int i=0;i<=n;++i)C[i][0]=C[i][i]=1;
for(int i=1;i<=n;++i)for(int j=1;j<i;++j)C[i][j]=Sum(C[i-1][j],C[i-1][j-1]);
mi[0]=mi[1]=1;
for(int i=2;i<=n;++i)mi[i]=Mul(mi[i-1],por(2,i-1));
H[1]=1;
for(int i=2;i<=n;++i){
H[i]=mi[i];
for(int j=1;j<i;++j)H[i]=Sub(H[i],C[i-1][j-1]*H[j]%mod*mi[i-j]%mod);
}
}
}
int main(){
poj1737::solve();
F[1][0]=1, G[1][1][0]=1;
for(int i=2;i<=n;++i){
for(int j=1;j<i;++j)for(int k=i-j;k;--k)for(int x=j;x;--x)
F[i][j]=Sum(F[i][j], F[k][0] * C[i-1][k-1]%mod * por(k,x)%mod * G[i-k][x][j-x]%mod);
F[i][0]=H[i];
for(int j=1;j<i;++j)F[i][0]=Sub(F[i][0],F[i][j]);
for(int j=1;j<=i;++j)for(int k=0;k<=i-j;++k){
if(j==1){
G[i][j][k]=F[i][k]*i%mod; continue;
}
for(int x=1;x<i;++x)for(int y=0;y<=k;++y)
G[i][j][k]=Sum(G[i][j][k], G[i-x][j-1][k-y]*C[i-1][x-1]%mod*G[x][1][y]%mod);
}
}
int ans=0;
for(int i=0;i<=m;++i) ans=Sum(ans,F[n][i]);
printf("%d\n",ans);
return 0;
}
暴力代码
#include<bits/stdc++.h>
typedef pair<int,int> pii;
using namespace std;
int n,m,bnum=0;
pii bian[666];
int to[33],nxt[33],first[33],tot=1;
int vis[33];
int del;
inline void add(int x,int y){
to[++tot]=y,nxt[tot]=first[x],first[x]=tot;
}
void makegraph(int x){
tot=1;memset(first,-1,sizeof(first));
for(int i=0;i<bnum;++i)if(x>>i&1){
int u=bian[i].first,v=bian[i].second;
add(u,v),add(v,u);
}
}
inline void dfs(int x){
vis[x]=1;
for(int i=first[x];~i;i=nxt[i])if(!vis[to[i]]&&i!=del&&i!=(del^1))dfs(to[i]);
}
inline bool can1(int d){
del=d;
memset(vis,0,sizeof(vis));
dfs(1);
for(int i=1;i<=n;++i)if(!vis[i])return 0;
return 1;
}
inline bool can(int x){
makegraph(x);
if(!can1(0))return 0;
int cnt=0;
for(int i=2;i<=tot;i+=2){
cnt+=!can1(i);
}
return cnt<=m;
}
int main(){
scanf("%d%d",&n,&m);
if(n>7)return 1;
if(m>n-1)m=n-1;
bnum=0;
for(int i=1;i<=n;++i)for(int j=i+1;j<=n;++j){
bian[bnum++]=pii(i,j);
}
int ans=0;
for(int i=0;i<(1<<bnum);++i){
ans+=can(i);
}
printf("%d\n",ans);
return 0;
}
听说是Tourist题？