斯坦纳树 – Qizy's Database

题目传送门：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;
}

Tag: 斯坦纳树

【BZOJ 4006】[JLOI2015] 管道连接

相关链接

解题报告

【BZOJ 2595】[Wc2008] 游览计划