B - A Funny Bipartite Graph

題意：

一個(gè)二分圖，左右各有n個(gè)點(diǎn)，左邊第i個(gè)點(diǎn)有一個(gè)屬性mi，它在一個(gè)圖中的價(jià)值為mi^di,其中di為它在圖中的度數(shù)(特殊的，如果度數(shù)為0，則價(jià)值為0)，求一個(gè)該二分圖的子圖使得右邊的每個(gè)點(diǎn)度數(shù)都不為0且總價(jià)值最小，輸出最小價(jià)值。如果無(wú)解輸出?1
有若干個(gè)限制條件(i,j)表示子圖中左邊的點(diǎn)i和j不能同時(shí)存在
保證：
原二分圖中左邊的每個(gè)點(diǎn)度數(shù)在[1,3]之間。
左邊的i點(diǎn)和右邊的j點(diǎn)連線當(dāng)且僅當(dāng)i ≤ j
n<=18
mi<=100

題解：

參考題解：
文章1
文章2
這個(gè)題的思路非常妙
首先根據(jù)數(shù)據(jù)范圍確定方法為狀壓dp
我們既要維護(hù)左側(cè)的點(diǎn)，也有維護(hù)右側(cè)的點(diǎn)，兩側(cè)都是n，我們都用二進(jìn)制取枚舉，那么復(fù)雜度就是n * 2²ⁿ,這樣肯定不行，要先辦法優(yōu)化
注意題目中有說(shuō)左側(cè)的i選右側(cè)的j，當(dāng)且僅當(dāng)i<=j,也就是說(shuō)當(dāng)我們考慮左側(cè)的第i個(gè)點(diǎn)時(shí)，左側(cè)的后n-i個(gè)還沒(méi)選，右側(cè)的前i個(gè)點(diǎn)必須全選(不然往后再也選不了)，也就是說(shuō)左側(cè)的后n-i位和右側(cè)的前i位都沒(méi)啥用，所有我們可以將左側(cè)的前i位和右側(cè)的后n-i位拼成一起，這樣2ⁿ就可以存下，復(fù)雜度就是O(n*2ⁿ)
這波操作就相當(dāng)于計(jì)組里面將32 位整數(shù)乘除法，它把乘數(shù)和結(jié)果同時(shí)存在了一個(gè) 64 位整數(shù)上
妙哉妙哉
思路很難，代碼也很難。。代碼之后更新

代碼:

#include<bits/stdc++.h> #define ll long long using namespace std; const int inf = 0x3f3f3f3f; int dp[2][1<<18]; int val[20], ban[20]; vector<int> g[20]; char s[20]; int n; void init(){scanf("%d", &n);for(int i = 0; i < n; ++i) g[i].clear();for(int i = 0; i < n; ++i) {scanf("%s", s);for(int j = 0; j < n; ++j) if(s[j] == '1') g[i].push_back(j);}for(int i = 0; i < n; ++i) {scanf("%s", s); ban[i] = 0;for(int j = 0; j < i; ++j) if(s[j] == '1') ban[i] |= (1<<j);}for(int i = 0; i < n; ++i) scanf("%d", &val[i]); } int sol(){int cur = 0, nxt = 1;memset(dp, 0x3f, sizeof dp);dp[cur][0] = 0;for(int i = 0; i < n; ++i){for(int mask = 0; mask < (1<<n); ++mask){int lstate = mask&((1<<i)-1);int rstate = mask&((1<<n)-(1<<i));if(dp[cur][mask] == inf) continue;// don't choose iif(rstate>>i&1) dp[nxt][(mask)^(1<<i)] = min(dp[nxt][(mask)^(1<<i)], dp[cur][mask]);if(ban[i]&lstate) continue;//can't choose ifor(int t = 1; t < (1<<g[i].size()); ++t){int cost = 1;int ex = 0;for(int j = 0; j < g[i].size(); ++j){int v = g[i][j];if(t>>j&1) cost *= val[i], ex |= 1<<v;}int nstate = rstate|ex;if( !(nstate>>i&1) ) continue;int sumstate=lstate|nstate;dp[nxt][sumstate] = min(dp[nxt][sumstate], dp[cur][mask] + cost);}}swap(cur, nxt);memset(dp[nxt], 0x3f, sizeof dp[nxt]);}int ans = inf;for(int i = 0; i < (1<<n); ++i) ans = min(ans, dp[cur][i]);if(ans == inf) return -1;return ans; } int main() {int T;cin>>T;while(T--){init();cout<<sol()<<endl;} } 創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來(lái)咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)

總結(jié)

以上是生活随笔為你收集整理的B - A Funny Bipartite Graph的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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