宿迁集团网站建设,网站备案授权书怎么填,建设摩托官方网站,dedecms免费网站模板正题
题目链接:https://www.luogu.com.cn/problem/P4294 题目大意 n∗mn*mn∗m的网格#xff0c;每个格子的修建费用不同#xff0c;要求修建费用最小连接所有关键点。 解题思路
设fs,i,jf_{s,i,j}fs,i,j表示目前连接关键点状态为sss#xff0c;在(i,j)(i,j)(i,j)这个位…正题
题目链接:https://www.luogu.com.cn/problem/P4294 题目大意
n∗mn*mn∗m的网格每个格子的修建费用不同要求修建费用最小连接所有关键点。 解题思路
设fs,i,jf_{s,i,j}fs,i,j表示目前连接关键点状态为sss在(i,j)(i,j)(i,j)这个位置时的最小代价然后同sss的用spfaspfaspfa转移即可。
输出方案记录一下前驱如果分裂开就分开两个赋值即可。
时间复杂度O(3knm)O(3^knm)O(3knm) codecodecode
#includecstdio
#includecstring
#includealgorithm
#includequeue
#define mp(x,y) make_pair(x,y)
using namespace std;
const int N13,S113;
const int dx[4]{1,-1,0,0},dy[4]{0,0,1,-1};
int n,m,cnt,a[N][N],g[N][N];
int f[S][N][N],pre[S][N][N];
bool v[N][N],w[N][N];
queuepairint,int q;
void SPFA(int s){for(int i1;in;i) for(int j1;jm;j)q.push(mp(i,j)),v[i][j]1;while(!q.empty()){int xq.front().first,yq.front().second;for(int k0;k4;k){int zxxdx[k],zyydy[k];if(zx1||zy1||zxn||zym)continue;if(f[s][x][y]a[zx][zy]f[s][zx][zy]){f[s][zx][zy]f[s][x][y]a[zx][zy];pre[s][zx][zy]-k-1;if(!v[zx][zy])q.push(mp(zx,zy)),v[zx][zy]1;}}q.pop();v[x][y]0;}return;
}
void dfs(int s,int x,int y){w[x][y]1;int zpre[s][x][y];if(!pre[s][x][y])return;if(z0)dfs(s,x-dx[-z-1],y-dy[-z-1]);else dfs(z,x,y),dfs(s-z,x,y);return;
}
int main()
{scanf(%d%d,n,m);for(int i1;in;i)for(int j1;jm;j){scanf(%d,a[i][j]);if(a[i][j]0)g[i][j]|(1(cnt));}int MS(1cnt);memset(f,0x3f,sizeof(f));for(int i1;in;i)for(int j1;jm;j)if(!a[i][j])f[g[i][j]][i][j]0;for(int s0;sMS;s){for(int i1;in;i)for(int j1;jm;j){int ls;while(l){l((l-1)s);if(!l)break;if(max(f[l][i][j],f[s-l][i][j])1e9)if(f[l][i][j]f[s-l][i][j]-a[i][j]f[s][i][j]){f[s][i][j]f[l][i][j]f[s-l][i][j]-a[i][j];pre[s][i][j]l;}}}SPFA(s);}int mx1,my1;for(int i1;in;i)for(int j1;jm;j)if(f[MS-1][i][j]f[MS-1][mx][my])mxi,myj;printf(%d\n,f[MS-1][mx][my]);dfs(MS-1,mx,my);for(int i1;in;i,putchar(\n))for(int j1;jm;j){if(!a[i][j])putchar(x);else if(w[i][j])putchar(o);else putchar(_);}
}
