對于一個連通塊，取一個點進行dfs，得到一棵dfs搜索樹，則這棵樹的深度不超過10，且所有額外邊都是前向邊。

對于每個點x，設S為三進制狀態，S第i位表示根到x路徑上深度為i的點的狀態：

0：選了

1：沒選，且沒滿足

2：沒選，且已滿足

設f[i][j]表示考慮根到x路徑上深度為i的點時這些點的狀態為j時的最小費用，然后按DFS序進行DP即可。

時間復雜度$O((n+m)3^{10})$，空間復雜度$O(10\times3^{10})$。

?

#include<cstdio> const int N=20010,M=50010,K=11,inf=2000000000; int n,m,i,x,y,a[N],g[N],v[M],nxt[M],ed,vis[N],d[N],q[K],pow[K],f[K][59050],ans; inline void add(int x,int y){v[++ed]=y;nxt[ed]=g[x];g[x]=ed;} inline int bit(int x,int y){return x/pow[y]%3;} inline void up(int&x,int y){if(x>y)x=y;} inline int min(int x,int y){return x<y?x:y;} void dfs(int x,int y){vis[x]=1,d[x]=y;if(!y)f[0][0]=a[x],f[0][1]=0,f[0][2]=inf;else{int cnt=0;for(int i=g[x];i;i=nxt[i]){int u=v[i];if(vis[u]&&d[u]<y)q[cnt++]=d[u];}for(int S=pow[y+1]-1;~S;S--)f[y][S]=inf;for(int S=pow[y]-1;~S;S--){int U=1,V=S;for(int i=0;i<cnt;i++)if(bit(S,q[i])==0)U=2;else if(bit(S,q[i])==1)V+=pow[q[i]];up(f[y][S+U*pow[y]],f[y-1][S]);up(f[y][V],f[y-1][S]+a[x]);}}for(int i=g[x];i;i=nxt[i]){int u=v[i];if(!vis[u]){dfs(u,y+1);for(int S=0;S<pow[y+1];S++)f[y][S]=min(f[y+1][S],f[y+1][S+2*pow[y+1]]);}} } int main(){for(pow[0]=i=1;i<K;i++)pow[i]=pow[i-1]*3;scanf("%d%d",&n,&m);for(i=1;i<=n;i++)scanf("%d",&a[i]);while(m--)scanf("%d%d",&x,&y),add(x,y),add(y,x);for(i=1;i<=n;i++)if(!vis[i])dfs(i,0),ans+=min(f[0][0],f[0][2]);return printf("%d",ans),0; }

　　

總結

以上是生活随笔為你收集整理的BZOJ3836 : [Poi2014]Tourism的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。