题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=2595
数据生成器:http://paste.ubuntu.com/23070779/
斯坦纳树第一题! 撒花~ *★,°*:.☆( ̄▽ ̄)/$:*.°★* 。
然而感觉斯坦纳树,撑死了算一类DP问题,为什么要叫算法呢QAQ
其实斯坦纳树,说白了就是一个状压DP?
题解的话,让我们召唤神犇:http://www.cnblogs.com/lidaxin/p/5299762.html
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define id(x,y) (((y)-1)*n+(x))
using namespace std;
const int MAXN = 19*19;
const int N = 2500;
const int INF = 0x3f3f3f3f;
int n,m,cnt,mat[MAXN],f[MAXN][N],num[MAXN],X,Y,vis[MAXN][N],pv,avl[MAXN];
queue<pair<int,int> > que;
pair<int,int> from[MAXN][N];
inline int read(){
char c=getchar(); int ret=0;
while (c<'0'||c>'9') c=getchar();
while (c<='9'&&c>='0') ret=ret*10+c-'0',c=getchar();
return ret;
}
inline void rev(int w){
Y = w / n + 1;
X = w - (Y-1)*n;
if (!X) X = n, Y--;
}
inline void update(int op, int nv, int pos, int w){
if (f[pos][w] > nv) {
f[pos][w] = nv;
from[pos][w] = make_pair(op,w);
if (!vis[pos][w]) vis[pos][w] = 1, que.push(make_pair(pos,w));
}
}
inline void SPFA(){
while (!que.empty()) {
rev(que.front().first);
int x=X, y=Y, w=que.front().second, pos=que.front().first;
vis[pos][w] = 0; que.pop();
if (x > 1) update(pos,f[pos][w]+mat[id(x-1,y)],id(x-1,y),w);
if (y > 1) update(pos,f[pos][w]+mat[id(x,y-1)],id(x,y-1),w);
if (x < n) update(pos,f[pos][w]+mat[id(x+1,y)],id(x+1,y),w);
if (y < m) update(pos,f[pos][w]+mat[id(x,y+1)],id(x,y+1),w);
}
}
inline void Steiner_Tree(){
for (int w=1,lim=1<<cnt;w<lim;w++) {
for (int j=1;j<=m;j++) for (int i=1;i<=n;i++) {
for (int k=w&(w-1);k;k=w&(k-1)) {
int tmp = f[id(i,j)][k] + f[id(i,j)][w^k] - mat[id(i,j)];
if (f[id(i,j)][w] > tmp) f[id(i,j)][w] = tmp, from[id(i,j)][w] = make_pair(id(i,j),k);
}
if (f[id(i,j)][w] != INF) que.push(make_pair(id(i,j),w)), vis[id(i,j)][w] = 1;
} SPFA();
}
}
void Mark_Ans(pair<int,int> tmp){
int pos=tmp.first, w = tmp.second; if (!pos) return;
rev(pos); int x = X, y = Y; avl[id(x,y)] = 1;
Mark_Ans(from[pos][w]);
if (from[pos][w].first == pos) Mark_Ans(make_pair(id(x,y),w-from[pos][w].second));
}
int main(){
m = read(); n = read();
for (int j=1;j<=m;j++) for (int i=1;i<=n;i++) {
memset(f[id(i,j)],0x3f,sizeof(f[id(i,j)]));
f[id(i,j)][0] = 0; mat[id(i,j)] = read();
if (!mat[id(i,j)]) f[id(i,j)][1<<cnt++] = 0, pv = id(i,j);
}
Steiner_Tree(); Mark_Ans(make_pair(pv,(1<<cnt)-1));
printf("%d\n",f[pv][(1<<cnt)-1]);
for (int j=1;j<=m;j++) {
for (int i=1;i<=n;i++)
if (!mat[id(i,j)]) putchar('x');
else if (avl[id(i,j)]) putchar('o');
else putchar('_');
putchar('\n');
}
return 0;
}