题目大意
给你 \(n\) 点 \(m\) 边的图，问有多少种删边方法使得 1 与 k 仍然联通。
\(1\le n\le 17, m\le \dfrac{n(n-1)}{2}\)
解题思路
看到 \(n\le 17\) ，显然是一道状压dp，但是 \(m\le 136\)，显然不能枚举边。
于是枚举点，显然的，有：连通图的数量=所有图的数量-非连通图的数量。
所以令 \(f_i,g_i\) 分别为只选 \(i\) 集合内的点和点之间的边的 连通图的数量与所有图的数量。
又所有图的数量为边之间随机连的个数，有 \(g_i=2^{\sum\limits_{e_j=\{u,v\}}{u\in i\land v\in i}}\)
如何计算 \(f_i\) 呢，根据上面的柿子，现在需要计算非联通图的数量，我们将图分为两部分，两部分之间不连边，就是一个非连通图。
但是可能重复计数，所以钦定一个点一定 \(v\) 在某一部分里，所以有非连通图的数量 \(h_i=\sum\limits_{j\subset all\land i\in j}{f_jg_{all\setminus j}}\)
所以有 \(f_i=g_i-h_i\)，状压即可。
怎么计算答案呢？显然是包含 \(1,k\) 的连通图加上其他的点构成的图就行了。
所以有 \(ans_i=\sum\limits_{j\subset i\land 1\in j\land k\in j}f_jg_{i\setminus j}\)
时间复杂度：因为计算 \(g\) 的复杂度为 \(O(m2^n)\)，枚举子集的子集的复杂度为 \(O(3^n)\)，计算答案复杂度为 \(O(n2^n)\) 所以总时间复杂度为 \(O(3^n+(n+m)2^n)\)
细节
- 注意计算答案的时候 \(1\) 和 \(k\) 要在连通图中。
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
const int N = 17, M = 200, p = 998244353;
int u[M], v[M], g[1 << N], f[1 << N], n, m;
ll qpow(ll a, ll b)
{
if(b == 0) return 1;
if(b == 1) return a;
return (b & 1) ? a * qpow(a * a % p, b >> 1) % p : qpow(a * a % p, b >> 1);
}
signed main()
{
ios::sync_with_stdio(0);cin.tie(0);
cin >> n >> m;
for(int i = 1; i <= m; i ++)
cin >> u[i] >> v[i];
int _2n = 1 << n;
for(int i = 0; i < _2n; i ++)
{
for(int j = 1; j <= m; j ++)
if(((1 << u[j] - 1) & i) && ((1 << v[j] - 1) & i))
g[i] ++;
g[i] = qpow(2, g[i]);
}
for(int i = 0; i < _2n; i ++)
{
f[i] = g[i];
int k = i & (-i);
for(int j = (i - 1) & i; j; j = (j - 1) & i)
if(j & k)
(f[i] -= f[j] * g[i ^ j]) %= p;
}
for(int i = 1; i < n; i ++)
{
int ans = 0;
for(int j = 1; j < _2n; j += 2)
if(j & (1 << i))
(ans += f[j] * g[(_2n - 1) ^ j]) %= p;
cout << (ans + p) % p << "\n";
}
return 0;
}