Description

給出一個具有N個結(jié)點的無向圖,將其分成兩個集合S1,S2. 這兩個集合的點的個數(shù)一樣多,但連接它們的邊最少.

Input

第一行給出數(shù)字N,M,代表有N個點,M條邊. 下面M行,每行兩個數(shù)字代表此兩點間有條邊.

Output

輸出的點集應(yīng)包含1，且按升序排列

Sample Input

6 8
1 2
1 6
2 3
2 5
2 6
3 4
4 5
5 6

Sample Output

1 2 6

HINT

N<=26

---

我還以為是狀壓DP... 因為$\binom{26}{13}$很小，所以可以直接爆搜。 我們每次從集合T內(nèi)抽取一個點放入S內(nèi)，直到S, T中都只有n/2個元素。 每次抽出一個點都計算這個點對答案產(chǎn)生的貢獻。 問題是如何在$O(1)$的時間內(nèi)算出貢獻。 顯然一個點從S到T內(nèi)，會減去它與S之間的邊，加上與T之間的邊。 我們對每個點用一個二進制數(shù)表示它所連的點的狀態(tài)，然后和集合狀態(tài)取與就是應(yīng)該減去/加上的邊的狀態(tài)。 然后統(tǒng)計數(shù)量直接預(yù)處理出每個二進制數(shù)的1的個數(shù)，但是1<<26太大了數(shù)組開不下。 只統(tǒng)計1<<13以內(nèi)的二進制數(shù)的1的個數(shù)，然后把狀態(tài)拆成兩半分別計算。

---

#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <queue> #include <algorithm> #include <bitset> using namespace std; #define reg register #define gc getchar inline int read() {int res=0;char ch=gc();bool fu=0;while(!isdigit(ch)){if(ch=='-')fu=1;ch=gc();}while(isdigit(ch))res=(res<<3)+(res<<1)+(ch^48), ch=gc();return fu?-res:res; }int n, m; int bin[27], cb[1<<14]; int sit[29]; int ans = 1e9, ansS;int Count(int x) {return cb[x>>13] + cb[(bin[13] - 1) & x]; }void dfs(int lst, int s1, int s2, int now, int num) {if (num == n / 2) {if (now < ans) ans = now, ansS = s1;return ;}for (reg int i = lst ; i <= n ; i ++){if (!(s2 & bin[i - 1])) continue;dfs(i + 1, s1 + bin[i - 1], s2 - bin[i - 1], now - Count(sit[i] & s1) + Count(sit[i] & s2), num + 1);} }int main() {n = read(), m = read();bin[0] = 1;for (reg int i = 1 ; i <= 26 ; i ++) bin[i] = bin[i - 1] << 1;for (reg int i = 1 ; i < bin[13] ; i ++) cb[i] = cb[i >> 1] + (i & 1);for (reg int i = 1 ; i <= m ; i ++){int x = read(), y = read();sit[x] |= bin[y - 1];sit[y] |= bin[x - 1];}dfs(1, 0, bin[n] - 1, 0, 0);if (!(ansS & bin[0])) ansS = (bin[n] - 1) ^ ansS;for (reg int i = 1 ; i <= n ; i ++)if (ansS & bin[i - 1]) printf("%d ", i);return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/BriMon/p/9785729.html

總結(jié)

以上是生活随笔為你收集整理的[BZOJ1130] [POI2008]POD Subdivision of Kingdom的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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