HDU5765 Bonds (高维前缀和)

题意：\(n(n<=20)\)个点\(m\)条边无向图，求每条边出现在多少个\(Bond\)里。一个图的\(cut\)指，对于一个图\(G\)的边集的某个子集\(E\)，如果删除\(E\)中的所有边，原图不连通。一个图的\(Bond\)指，对于一个图\(G\)，\(cut\)恰好使得图不连通的边集\(E\)，即原图去除\(E\)后，形成两个连通图。

做法：首先，考虑如何求出所有的\(Bond\)。显然可以\(2^{20}\)枚举出点集\(A\)，然后如果\(A\)和它的补集\(B\)，分别都是联通的，那么他们之间的所有边构成一种合法的\(Bond\)。这里就需要预处理点集的联通形\(ok[s]\)。之后，考虑如何计算每条边出现在多少个\(Bond\)里，一种显然会\(TLE\)的方法是枚举所有的边和\(Bond\)，即\(O(m2^n)\)。考虑对于一条边\(u-v\)的答案，就是在所有合法的\(Bond\)中，\(u\)和\(v\)分别属于\(Bond\)的两边。也就等于，所有的\(Bond\)的数目，去掉\(u-v\)都在一个集合内的数目。我们用\(f[s]\)表示，包含点集\(s\)的所有合法的集合的数目，显然可以先\(f[合法点集]=1\)，然后做超集的高维前缀和，而\(f[(1<就是包含\(u-v\)的合法集合的数目，用总的Bond数减去它就是该条边的答案。另外还有个坑点，一开始直接\(bfs\)这个图求\(ok[s]\)，就\(TLE\)

#include 
#include 
#include 
#include 
#include 
#include 
#define IOS ios::sync_with_stdio(false)
#define pb push_back
#define Pii pair
#define Ppi pair
#define x first
#define y second
typedef long long ll;
const int N = 20;
inline void read(int &x) {
    x = 0; int f = 1; char c = getchar();
    while(!isdigit(c)) {if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)) {x=x*10+c-'0';c=getchar();}
    x *= f;
}
using namespace std;
int n, m, LIM, u[444], v[444], f[1 << N | 5], G[N+3];
bool ok[1 << N | 5];
void init_ok() {
    for(int i = 0; i < n; ++i) ok[1<

for(int j = 0; j < n; ++j) 
    for(int i = 0; i < (1 << n); ++i) 
        if(!(i & (1 << j))) f[i] += f[i|(1<

for(int j = 0; j < n; ++j)
    for(int i = 0; i< (1 << n); ++i)
        if(i & (1 << j)) f[i] += f[i^(1<