2595: [Wc2008]游览计划
Time Limit: 10 Sec Memory Limit: 256 MBSec Special JudgeSubmit: 1735 Solved: 829
Description
Input
第一行有两个整数，N和 M，描述方块的数目。
接下来 N行， 每行有 M 个非负整数， 如果该整数为 0， 则该方块为一个景点；否则表示控制该方块至少需要的志愿者数目。 相邻的整数用 （若干个） 空格隔开，行首行末也可能有多余的空格。Output
由 N + 1行组成。第一行为一个整数，表示你所给出的方案
中安排的志愿者总数目。 接下来 N行，每行M 个字符，描述方案中相应方块的情况： z ‘_’（下划线）表示该方块没有安排志愿者； z ‘o’（小写英文字母o）表示该方块安排了志愿者； z ‘x’（小写英文字母x）表示该方块是一个景点； 注：请注意输出格式要求，如果缺少某一行或者某一行的字符数目和要求不一致（任何一行中，多余的空格都不允许出现） ，都可能导致该测试点不得分。Sample Input
Sample Output
HINT
对于100%的数据，N,M,K≤10，其中K为景点的数目。输入的所有整数均在[0,2^16]的范围内。
窝发现窝好弱啊。下午学了一波斯坦纳树，打了一下模板题BZOJ4774修路，感觉十分膨胀，于是去做了一下杭电的桃花源记，让我构建斯坦纳森林，就不会了。现在又要我输出路径，又是看了题解才会的。大家一起%吧。
其实这题除了输出路径以外都不难，貌似就是一道裸的斯坦纳树板子题加了点路径特技。
斯坦纳树的实现原理类似子集DP，是一个求关键点连通问题的优秀解法。所谓关键点连通，就是指要求的一些点必须连通，但不一定只有这一些点。斯坦纳树是用子集DP+SPFA的原理解决这一问题。当然，关键点数目必须不大(因为每一个点都是一个二进制位0/1)。
首先对初始的关键点赋好值(f[i][1<<k]=0)，然后从小到大枚举全集(opt)。在每一次枚举全集内，因为子集sub肯定被枚举过(因为定有sub<opt)，所以可以用子集的并的方式更新自己的opt值，这就是斯坦纳树的第一个转移方程：
f[i][opt]=min{f[i][sub]+f[i][opt^sub,sub∈opt};
自我枚举后就可以对这一状态的点集进行spfa，用f[i][opt]维护f[j][opt]。这就是第二个方程：
f[i][opt]=min{f[j][opt]+dis(i,j)};
这样对于每一个集合的值就已经求出来了。最后统计一边答案即可。
对于这道题的路径输出，hzwer -> zky ->姜碧野的代码里是把斯坦纳树的每一次取min都记下转移的来源，然后随便找个景点开始按照转移的顺序反向dfs，打上vis标记来输出。
一辈子也想不到啊想不到。
具体代码就在下面了。你不得不承认斯坦纳树写起来还是很优美的... ...
#include#include #include #include #include #include #include #include #include #define LL long long int#define dob doubleusing namespace std; const int N = 12;const int M = 1024;const int Inf = 707406378;struct Node{int x,y;}trav[M];struct Data{int x,y,set;}from[N][N][M];int n,m,k,In[N][N],f[N][N][M],map[N][N],full,ans[M],pot[N];int gx[]={0,0,0,1,-1},gy[]={0,1,-1,0,0},vis[N][N];queue Q; int gi(){ int x=0,res=1;char ch=getchar(); while(ch>'9'||ch<'0'){if(ch=='-')res*=-1;ch=getchar();} while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar(); return x*res;} inline void spfa(int opt){ while(!Q.empty()){ Node now=Q.front();Q.pop(); int x=now.x,y=now.y;In[x][y]=0; for(int e=1;e<=4;++e){ int nx=x+gx[e],ny=y+gy[e]; if(x<1 || y<1 || x>n || y>m)continue; if(f[nx][ny][opt]>f[x][y][opt]+map[nx][ny]){ f[nx][ny][opt]=f[x][y][opt]+map[nx][ny]; from[nx][ny][opt]=(Data){x,y,opt}; if(!In[nx][ny])Q.push((Node){nx,ny}),In[nx][ny]=1; } } }}inline void dfs(int x,int y,int kind){ vis[x][y]=1; Data g=from[x][y][kind]; if(!g.x || !g.y)return; dfs(g.x,g.y,g.set); if(x==g.x && y==g.y) dfs(g.x,g.y,kind^g.set);}inline void work(){ full=(1<