傳送門：http://www.lydsy.com/JudgeOnline/problem.php?id=4006

思路：

一眼看上去很像斯坦納樹

但是限制稍有不同，只要每種顏色的點聯通即可

也就是說最后可能是森林

我聽說裸寫斯坦納樹有90

所以我們要在外面再套一層DP

f[i][j]還是斯坦納樹的狀態，i是以i為根，j是狀態為j

先用斯坦納樹求出每種聯通狀況的最小費用

再設dp[i]表示i這個狀態的最小費用

枚舉子集時保證顏色相同的連通性相同，轉移即可

dp[i]=min(dp[j]+dp[i-j])j是i的子集

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> const int maxn=11,maxk=11,maxq=105; const int dx[]={0,0,1,-1},dy[]={1,-1,0,0}; using namespace std; int n,m,K,head,tail,cnt,pw[maxk+5],w[maxk],q[maxq+10],f[maxn][maxn][1<<maxk],pre[maxn][maxn][1<<maxk],a[maxn][maxn],inf; bool bo[maxn][maxn],vis[maxn][maxn]; inline bool in(int x,int y){return x>=0&&x<n&&y>=0&&y<m;} inline int id(int x,int y){return x*10+y;} inline int id2(int x,int y,int s){return s*100+x*10+y;} inline void decode(int sta,int &x,int &y){x=sta/10,y=sta%10;} inline void decode2(int sta,int &x,int &y,int &s){s=sta/100,x=sta%100/10,y=sta%10;}void init(){pw[0]=1;for (int i=1;i<=11;i++) pw[i]=pw[i-1]<<1;scanf("%d%d",&n,&m);for (int i=0;i<n;i++)for (int j=0;j<m;j++){scanf("%d",&a[i][j]);if (!a[i][j]) w[K++]=id(i,j);} }void spfa(int s){//printf("s=%d\n",s);while (head!=tail){if (++head>maxq) head=1;int sta=q[head],x,y;decode(sta,x,y);//printf("x=%d y=%d\n",x,y);for (int i=0;i<4;i++){int nx=x+dx[i],ny=y+dy[i];if (!in(nx,ny)) continue;//printf("nx=%d ny=%d\n",nx,ny);if (f[nx][ny][s]>f[x][y][s]+a[nx][ny]){f[nx][ny][s]=f[x][y][s]+a[nx][ny];//printf("ffffffffffffffffffffffffffffff=%d\n",f[nx][ny][s]);pre[nx][ny][s]=id2(x,y,s);if (!bo[nx][ny]){if (++tail>maxq) tail=1;bo[nx][ny]=1,q[tail]=id(nx,ny);}}}bo[x][y]=0;} }void dfs(int i,int s){int x,y,nx,ny,t;decode(i,x,y);//printf("x=%d y=%d s=%d\n",x,y,s);vis[x][y]=1;if (!pre[x][y][s]) return;//printf("%d %d\n",id2(x,y,s),pre[x][y][s]);decode2(pre[x][y][s],nx,ny,t);//printf("px=%d py=%d pt=%d\n",nx,ny,t);dfs(id(nx,ny),t);if (x==nx&&y==ny) dfs(id(nx,ny),s^t); }void work(){memset(f,63,sizeof(f)),inf=f[0][0][0];for (int i=0,x,y;i<K;i++){decode(w[i],x,y);f[x][y][pw[i]]=0;}for (int sta=1;sta<pw[K];sta++){head=tail=0;for (int i=0;i<n;i++)for (int j=0;j<m;j++){for (int s=sta&(sta-1);s;s=(s-1)&sta)if (f[i][j][sta]>f[i][j][s]+f[i][j][sta^s]-a[i][j]){f[i][j][sta]=f[i][j][s]+f[i][j][sta^s]-a[i][j];pre[i][j][sta]=id2(i,j,s);}if (f[i][j][sta]!=inf) q[++tail]=id(i,j),bo[i][j]=1;//printf("x=%d y=%d sta=%d f=%d\n",i,j,sta,f[i][j][sta]);}spfa(sta);}int x,y;decode(w[0],x,y);//printf("xx=%d yy=%d sta=%d\n",x,y,pw[K]-1);printf("%d\n",f[x][y][pw[K]-1]);int nx,ny,ns;decode2(pre[x][y][pw[K]-1],nx,ny,ns);//printf("nx=%d ny=%d ns=%d\n",nx,ny,ns);dfs(w[0],pw[K]-1);for (int i=0;i<n;i++,puts(""))for (int j=0;j<m;j++)if (!a[i][j]) putchar('x');else if (vis[i][j]) putchar('o');else putchar('_'); }int main(){//freopen("test.in","r",stdin);freopen("test.out","w",stdout);init(),work();return 0; } /* 8 8 1 4 1 3 4 2 4 1 4 3 1 2 0 1 2 3 3 2 1 3 0 3 1 2 2 6 5 0 2 4 1 0 5 1 2 1 3 4 2 5 5 1 3 1 5 0 1 4 5 0 6 1 4 5 3 4 0 2 2 2 3 4 1 1*/

轉載于:https://www.cnblogs.com/thythy/p/5493626.html

總結

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

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