Luogu 4294 [WC2008]游览计划

题目链接

Luogu 4294

（我做这道题的时候BZOJ全站的SPJ都炸了提交秒WA 幸好有洛谷）

题解

这道题是【斯坦纳树】的经典例题。斯坦纳树是这样一类问题：带边权无向图上有几个（一般约10个）点是【关键点】，要求选择一些边使这些点在同一个联通块内，同时要求所选的边的边权和最小。

怎么解决斯坦纳树问题？……其实，就是一种状压DP。

\(dp[i][j]\)表示以i号节点为根，当前状态为j（j的二进制中已经与i连通的点对应位置为1）。

这个“以i为根”是哪来的呢？其实i可以是联通块中任意一个点，没有额外限制，只是引入这个i就可以DP了。

当根i不改变时（即合并两个都包含i的联通块）状态转移方程是：

\[dp[i][j] = \min_{s \in j}\{dp[i][s] + dp[i][\complement_js] - val[i]\}
\]

（\(val[i]\)表示本题中i号点的权值，减去一个是因为\(dp[i][s]\)和\(dp[i][\complement_js]\)中都含有i号点的权值，要防止“加重了”）

当根改变时（即在原有联通块中加入一个新节点i并设置为根，要求i、k相邻）：

\[dp[i][j] = \min\{dp[k][j] + val[i]\}
\]

第一个状态转移方程有顺序，可以直接DP；而第二个状态转移方程没有明显顺序，但可以按照最短路的SPFA算法“DP”（神奇！）。

代码

#include <cstdio>

#include <cstring>

#include <cmath>

#include <algorithm>

#include <iostream>

#include <queue>

#define space putchar(' ')

#define enter putchar('\n')

using namespace std;

typedef long long ll;

template <class T>

void read(T &x){

    char c;

    bool op = 0;

    while(c = getchar(), c < '0' || c > '9')

    if(c == '-') op = 1;

    x = c - '0';

    while(c = getchar(), c >= '0' && c <= '9')

    x = x * 10 + c - '0';

    if(op) x = -x;

}

template <class T>

void write(T x){

    if(x < 0) putchar('-'), x = -x;

    if(x >= 10) write(x / 10);

    putchar('0' + x % 10);

}

const int INF = 0x3f3f3f3f;

int n, m, K, root, f[101][1111], a[101], ans[11][11];

bool inq[101];

typedef pair<int, int> par;

typedef pair<par, int> rec;

#define fi first

#define se second

#define mp make_pair

#define num(u) (u.fi * m + u.se)

rec pre[101][1111];

const int dx[] = {0, 0, -1, 1};

const int dy[] = {1, -1, 0, 0};

queue<par> que;

bool legal(par u){

    return u.fi >= 0 && u.se >= 0 && u.fi < n && u.se < m;

}

void spfa(int now){

    while(!que.empty()){

	par u = que.front();

	que.pop();

	inq[num(u)] = 0;

	for(int d = 0; d < 4; d++){

	    par v = mp(u.fi + dx[d], u.se + dy[d]);

	    int nu = num(u), nv = num(v);

	    if(legal(v) && f[nv][now] > f[nu][now] + a[nv]){

		f[nv][now] = f[nu][now] + a[nv];

		if(!inq[nv]) inq[nv] = 1, que.push(v);

		pre[nv][now] = mp(u, now);

	    }

	}

    }

}

void dfs(par u, int now){

    if(!pre[num(u)][now].se) return;

    ans[u.fi][u.se] = 1;

    int nu = num(u);

    if(pre[nu][now].fi == u) dfs(u, now ^ pre[nu][now].se);

    dfs(pre[nu][now].fi, pre[nu][now].se);

}

int main(){

    read(n), read(m);

    memset(f, 0x3f, sizeof(f));

    for(int i = 0, tot = 0; i < n; i++)

	for(int j = 0; j < m; j++){

	    read(a[tot]);

	    if(!a[tot]) f[tot][1 << (K++)] = 0, root = tot;

	    tot++;

	}

    for(int now = 1; now < (1 << K); now++){

	for(int i = 0; i < n * m; i++){

	    for(int s = now & (now - 1); s; s = now & (s - 1))

		if(f[i][now] > f[i][s] + f[i][now ^ s] - a[i]){

		    f[i][now] = f[i][s] + f[i][now ^ s] - a[i];

		    pre[i][now] = mp(mp(i / m, i % m), s);

		}

	    if(f[i][now] < INF)

		que.push(mp(i / m, i % m)), inq[i] = 1;

	}

	spfa(now);

    }

    write(f[root][(1 << K) - 1]), enter;

    dfs(mp(root / m, root % m), (1 << K) - 1);

    for(int i = 0, tot = 0; i < n; i++){

	for(int j = 0; j < m; j++)

	    if(!a[tot++]) putchar('x');

	    else putchar(ans[i][j] ? 'o' : '_');

	enter;

    }

    return 0;

}

巴特西

Luogu 4294 [WC2008]游览计划 | 斯坦纳树

题目链接

题解

代码

最新文章

热门文章