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才有可能存在方案，故初始化：
memsetf,0,sizeoff)),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!isdigitch))
{
f|=ch=='-');
ch=getchar);
}
whileisdigitch))
{
s=s<<3)+s<<1)+ch^48);
ch=getchar);
}
return f)?-s):s);
}
inline void writeint x)
{
ifx<0)
{
putchar'-');
x=-x;
}
ifx<10)
{
putcharx+'0');
return;
}
writex/10);
putcharx%10)+'0');
return;
}
/*
inline void writelnint x)
{
writex);
putchar'
');
return;
}*/
int main)
{
n=read);m=read),k=read);
forint 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;
//初始时，树中只有两边一点，两个点都是叶子结点
}
forint 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;
forint j=i;j;j=j-1)&i) //枚举叶节点，叶节点一定得比树中节点少
{
if!f[i][j]) continue;
forint x=0;x<=n-1;x++)
{
if!i&1<<x))) continue;
t=j&1<<x)?j^1<<x):j;
forint y=0;y<=n-1;y++)
{
if!a[x][y]||i&1<<y))||t>1<<y)));//保证新加入的节点编号一定比树中节点大，有序就可去重
}
}
}
forint j=1;j<=1<<n)-1;j++)
{
s=0;
t=j;
whilet)
{
s+=t&1;
t>>1;
}
ifs==k) ans+=f[1<<n)-j][j];
}
writeans);
return 0;
}