洛谷題目頁面傳送門 & AtCoder題目頁面傳送門
給定一個無向連通帶權圖\(G=(V,E),|V|=n,|E|=m\)（節點從\(0\)開始編號），要刪掉一些邊使得節點\(0\)到\(n-1\)有且只有\(1\)條簡單路徑，求最小的刪掉的邊的權值和，
\(n\in[2,15],m\in\left[n-1,\dfrac{n(n-1)}2\right]\)，\(G\)中沒有重邊或自環，
這個問題顯然可以轉化為：求最大的刪過邊之后的圖的邊權和，再用原圖的邊權和減去它，
考率刪過邊之后的圖\(G'(V,E')\)的樣子，\(0\to n-1\)只有\(1\)條簡單路徑，設它為\(pa\left(pa_1=0,pa_s=n-1,\forall i\in[1,s),(pa_i,pa_{i+1},len)\in E'\right)\)，若\(\exists i\in[1,s],\exists j\in[i+1,s]\)，\(pa_i\to pa_j\)有不止\(1\)條簡單路徑，那么顯然可以先走\(0\to pa_i\)，然后分別走\(pa_i\to pa_j\)的多條路徑，最后走\(pa_j\to n-1\)，構造出多條\(0\to n-1\)路徑，不符合題意，可以得到\(\forall i\in[1,s],\forall j\in[i+1,s]\)，\(pa_i\to pa_j\)只有\(1\)條簡單路徑，所以\(G'\)應該是這樣的：\(pa\)中每個點下面掛著幾坨連通的點，各個點掛的點集沒有交集（如果有交集，那么這\(2\)個\(pa\)中的點之間的簡單路徑就會不止\(1\)條），
最優情況下，\(G'\)一定是連通的，理由：若\(G'\)不連通，由于\(G'\)合法，\(0,n-1\)一定在一個連通分量內，那么可以在除了\(0,n-1\)所在連通分量的其他連通分量之間恢復若干被洗掉的邊使得它們連通（由于原圖\(G\)連通，一定可行），此時\(G'\)還剩\(2\)個連通分量，設它們分別為\(A,B\)，其中\(0,n-1\in A\)，由于原圖\(G\)連通，一定可以找到一組點\((a,b)\)使得\(a\in A,b\in B,(a,b,len)\in E\)，將\((a,b,len)\)恢復，這樣\(B\)就成為了掛在\(pa\)中點下新的一坨點或某坨舊點的一份子，如此，可以在\(G'\)上恢復若干被洗掉的邊，使得它更優且合法，所以最優情況下，\(G'\)一定是連通的，
接下來，利用任意\(2\)坨點都沒有交集這個性質，就可以狀壓DP了，設\(dp_{i,j}(0\in i)\)表示\(pa\)中\(0\to j\)這條鏈包括它們下面掛的那些坨點所構成的點集為bitmask\(i\)時，\(\left\{(x,y,len)\mid x,y\in i,(x,y,len)\in E\right\}\)中可以留下的邊的最大權值和，顯然，目標為\(\sum\limits_{(x,y,len)\in E}len-dp_{V,n-1}\)，邊界為\(dp_{i,0}=\sum\limits_{x,y\in i,(x,y,len)\in E}len\)，轉移時，列舉\(j\)下掛的點集，這個點集和\(\{j\}\)的并集中顯然應該所有的邊都留下，再列舉\(pa\)中\(j\)的前一個點，這個點到\(j\)的邊也應該留下，于是狀態轉移方程就出來了：
\[dp_{i,j}=\max_{k\subseteq i-\{0,j\}}\left\{\sum_{x,y\in k\cup\{j\},(x,y,len)\in E}len+\max_{o\in i-k-\{j\},(o,j,len)\in E}\left\{len+dp_{i-k-\{j\},o}\right\}\right\} \]
這里面有個子集列舉，所以直接按照這個方程轉移是\(\mathrm O\!\left(3^nn^3\right)\)的，過不去，顯然，可以預處理出\(sum_i=\sum\limits_{x,y\in i,(x,y,len)\in E}len\)，復雜度降到了\(\mathrm O\!\left(3^nn^2\right)\)，但還是過不去，接下來要處理\(\max\limits_{o\in i-k-\{j\},(o,j,len)\in E}\left\{len+dp_{i-k-\{j\},o}\right\}\)，不難發現這個式子僅關于\(i-k-\{j\}\)和\(j\)，而不同的二元組\((i-k-\{j\},j)\)只有\(\mathrm O(2^nn)\)個，這個式子卻被計算了\(\mathrm O(3^nn)\)次，于是我們可以避免重復計算，記錄\(tmp_{i,j}=\max\limits_{k\in i,(k,j,len)\in E}\left\{len+dp_{i,k}\right\}\)，在每次完成一個\(dp_{i,j}\)的計算時，更新所有與它相關的\(tmp\)的值，即令\(\forall k\notin i((j,k,len)\in E),tmp_{i,k}=\max(tmp_{i,k},len+dp_{i,j})\)，這樣，在狀態轉移方程中遇到這個式子時，直接呼叫\(tmp\)即可，
放一下最終的狀態轉移方程：
\[dp_{i,j}=\max_{k\subseteq i-\{0,j\}}\!\left\{sum_{k\cup\{j\}}+tmp_{i-k-\{j\},j}\right\} \]
時間復雜度\(\mathrm O\!\left(3^nn+2^nn^2\right)=\mathrm O(3^nn)\)，
最后上代碼：
#include<bits/stdc++.h>
using namespace std;
const int inf=0x3f3f3f3f;
const int N=15;
int n,m;
int tb[N][N];//鄰接矩陣
int sum[1<<N];
int tmp[1<<N][N],dp[1<<N][N];
void prt_bitmsk(int x){
for(int i=0;i<n;i++)cout<<!!(x&1<<i);
}
int main(){
cin>>n>>m;
int tot=0;
while(m--){
int x,y,z;
cin>>x>>y>>z;
x--;y--;
tb[x][y]=tb[y][x]=z;
tot+=z;
}
for(int i=0;i<1<<n;i++){//預處理sum
for(int j=0;j<n;j++)if(i&1<<j)for(int k=j+1;k<n;k++)if(i&1<<k)
sum[i]+=tb[j][k];
// printf("sum[");prt_bitmsk(i);printf("]=%d\n",sum[i]);
}
for(int i=0;i<1<<n;i++)for(int j=0;j<n;j++)dp[i][j]=tmp[i][j]=-inf;//初始化
for(int i=0;i<1<<n;i++)if(i&1)for(int j=0;j<n;j++)if(i&1<<j){//DP
if(j)//非邊界
for(int k=i^1<<j^1;;k=k-1&(i^1<<j^1)){//列舉j下面掛的點集k
dp[i][j]=max(dp[i][j],sum[k|1<<j]+tmp[i^k^1<<j][j]);//狀態轉移方程
if(!k)break;
}
else//邊界
dp[i][j]=sum[i];
// printf("dp[");prt_bitmsk(i);printf("][%d]=%d\n",j,dp[i][j]);
for(int k=0;k<n;k++)if(!(i&1<<k))//更新與dp[i][j]有關的所有tmp[i][k]
if(tb[j][k])
tmp[i][k]=max(tmp[i][k],dp[i][j]+tb[j][k]);
}
cout<<tot-dp[(1<<n)-1][n-1];//目標
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/61734.html
標籤：C++