1781：死亡之树
时间限制: 1000 ms 内存限制: 262144 KB
提交数: 99 通过数: 70
【题目描述】
如果一个n个点，m条无向边的图中(保证没有重边)的若干个点与连接它们的边组成的一棵树满足n个节点，k
个叶子，则称这棵树为死亡之树。求这个图中有多少棵不同的死亡之树？
叶子的定义:度数为1的节点。
树相同的定义：如果两棵树可以通过摆放，旋转转化为另一棵树的形状，则称之为相同的树。如 与1−2−3为相同的一棵树。
2
/
1 3
【输入】
第一行两个整数n，m，k代表n个点m条边，最终需要有k个叶子；
接下来m行每行两个整数a，b表示a点与b点有一条边。
【输出】
一个整数，代表有多少棵死亡之树。
【输入样例】
3 3 2
1 2
2 3
1 3
【输出样例】
3
【提示】
【样例输入2】
4 6 3
1 2
2 3
3 4
4 1
1 3
2 4
【样例输出2】
4
【数据规模及约定】
对于40%的数据：n≤10，m≤16
对于70%的数据：n≤10，m≤23
对于100%的数据：n≤10，m≤45
思路：
1.算法分析：
发现节点数n<=10，可以用状压，设f[i][j]表示存入节点集合为i，叶节点集合为j，用二进制表示节点状态；
2.初始化：
因为叶子结点定义是入度为1的点，所以当前树的个数一定大于等于2才有可能存在方案，故初始化：
memset(f,0,sizeof(f)),f[(1<<x)|(1<<y)][(1<<y)|(1<<y)]=1;
3.转移：
枚举当前状态，枚举树中节点x，再枚举与x相连的，不在树内的节点y，则新加入的节点y在树内做叶节点（因为其入度为1），所以状态数为j|(1<<y)
特殊的，因为原来的节点x在树中有可能是叶节点，所以应排除x是叶节点的情况，故最终状态为（j^(1<<x)|(1<<y)）
[为了简化，我们可以在枚举y之前先判断x在树中是否是叶节点，如果是，先把x删去。设置一个t表示t=j&(1<<x)?j^(1<<x)，j]
4.去重：
什么情况下会有重复的情况呢，只有在加入边x1 y1，x2 y2时，会出现两种情况：先加1，后加2；先加2，后加1。这样的话只要我们限制更新顺序，就不会有重复的情况发生；
最终状态转移方程：
f[i|(1<<y)][t|(1<<y)]+=f[i][j]
(f[i][j]&&(x->y)&&(i&(i<<x))&&!(i&(1<<y))&&(t<(1<<y)))
代码：
#include<bits/stdc++.h>
using namespace std;
const int N=10,M=1<<N;
int f[M][M],n,m,k,tot,x,y,t,s,ans;
bool a[N][N];
inline int read()
{
int s=0;
bool f=0;
char ch=' ';
while(!isdigit(ch))
{
f|=(ch=='-');
ch=getchar();
}
while(isdigit(ch))
{
s=(s<<3)+(s<<1)+(ch^48);
ch=getchar();
}
return (f)?(-s):(s);
}
inline void write(int x)
{
if(x<0)
{
putchar('-');
x=-x;
}
if(x<10)
{
putchar(x+'0');
return;
}
write(x/10);
putchar((x%10)+'0');
return;
}
/*
inline void writeln(int x)
{
write(x);
putchar('
');
return;
}*/
int main()
{
n=read();m=read(),k=read();
for(int i=1;i<=m;i++)
{
x=read()-1;
y=read()-1;
a[x][y]=a[y][x]=true;
f[(1<<x)|(1<<y)][(1<<x)|(1<<y)]=1;
//初始时，树中只有两边一点，两个点都是叶子结点
}
for(int i=1;i<=(1<<n)-1;i++)//i<=(1<<n)-1是因为总共有0~n-1个节点，1<<(n-1)的方案数，而下面的j枚举的是叶子节点的状态，为 1~1<<(n-1)（至少得有一个叶节点），为了
//让(j-1)=1<<(n-1),i=(1<<n)-1;
for(int j=i;j;j=(j-1)&i) //枚举叶节点，叶节点一定得比树中节点少
{
if(!f[i][j]) continue;
for(int x=0;x<=n-1;x++)
{
if(!(i&(1<<x))) continue;
t=j&(1<<x)?j^(1<<x):j;
for(int y=0;y<=n-1;y++)
{
if(!a[x][y]||(i&(1<<y))||(t>(1<<y)));//保证新加入的节点编号一定比树中节点大，有序就可去重
}
}
}
for(int j=1;j<=(1<<n)-1;j++)
{
s=0;
t=j;
while(t)
{
s+=t&1;
t>>1;
}
if(s==k) ans+=f[(1<<n)-j][j];
}
write(ans);
return 0;
}