HDU5765 Bonds (高維前綴和)

---

題意：\(n(n<=20)\)個點\(m\)條邊無向圖，求每條邊出現(xiàn)在多少個\(Bond\)里。一個圖的\(cut\)指，對于一個圖\(G\)的邊集的某個子集\(E\)，如果刪除\(E\)中的所有邊，原圖不連通。一個圖的\(Bond\)指，對于一個圖\(G\)，\(cut\)恰好使得圖不連通的邊集\(E\)，即原圖去除\(E\)后，形成兩個連通圖。

做法：首先，考慮如何求出所有的\(Bond\)。顯然可以\(2^{20}\)枚舉出點集\(A\)，然后如果\(A\)和它的補(bǔ)集\(B\)，分別都是聯(lián)通的，那么他們之間的所有邊構(gòu)成一種合法的\(Bond\)。這里就需要預(yù)處理點集的聯(lián)通形\(ok[s]\)。之后，考慮如何計算每條邊出現(xiàn)在多少個\(Bond\)里，一種顯然會\(TLE\)的方法是枚舉所有的邊和\(Bond\)，即\(O(m2^n)\)。考慮對于一條邊\(u-v\)的答案，就是在所有合法的\(Bond\)中，\(u\)和\(v\)分別屬于\(Bond\)的兩邊。也就等于，所有的\(Bond\)的數(shù)目，去掉\(u-v\)都在一個集合內(nèi)的數(shù)目。我們用\(f[s]\)表示，包含點集\(s\)的所有合法的集合的數(shù)目，顯然可以先\(f[合法點集]=1\)，然后做超集的高維前綴和，而\(f[(1<<u)|(1<<v)]\)就是包含\(u-v\)的合法集合的數(shù)目，用總的Bond數(shù)減去它就是該條邊的答案。另外還有個坑點，一開始直接\(bfs\)這個圖求\(ok[s]\)，就\(TLE\)

#include <cstdio> #include <algorithm> #include <iostream> #include <vector> #include <queue> #include <cstring> #define IOS ios::sync_with_stdio(false) #define pb push_back #define Pii pair<int,int> #define Ppi pair<Pii, int> #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<<i] = 1;for(int s = 0; s < (1<<n); ++s) {if(!ok[s]) continue;for(int i = 0; i < n; ++i) if( !(s&(1<<i)) && (s&G[i]) ) ok[s|(1<<i)] = 1;} } int main() {int T_T, KK = 0; read(T_T);while(T_T--) {read(n), read(m);LIM = (1<<n)-1;memset(G,0,sizeof(G));memset(ok,0,sizeof(ok)); memset(f,0,sizeof(f));for(int i = 0; i < m; ++i) {read(u[i]), read(v[i]);G[u[i]] |= (1<<v[i]);G[v[i]] |= (1<<u[i]);}init_ok();int ans = 0;for(int s = 0; s <= LIM-s; ++s) if(ok[s] && ok[LIM-s]) {++ ans; f[s] = f[LIM-s] = 1;}for(int j = 0; j < n; ++j) for(int i = 0; i <= LIM; ++i) if(!(i & (1 << j))) f[i] += f[i|(1<<j)];printf("Case #%d:",++KK);for(int tmp, i = 0; i < m; ++i) {printf(" %d", ans - f[(1<<u[i])|(1<<v[i])]);} putchar('\n');} }

高維前綴和模板

超集

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

子集

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

轉(zhuǎn)載于:https://www.cnblogs.com/RRRR-wys/p/10330875.html

總結(jié)

以上是生活随笔為你收集整理的HDU5765 Bonds (高维前缀和)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。