斯坦纳树小结

斯坦纳树

网上关于这玩意儿的资料不是很多

度娘的定义

斯坦纳树问题是组合优化问题,与最小生成树相似,是最短网络的一种。 最小生成树是在给定的点集和边中寻求最短网络使所有点连通。 而最小斯坦纳树允许在给定点外增加额外的点,使生成的最短网络开销最小。

我个人认为这玩意儿应该是某一类没有多项式解法的最小生成树问题,然后可以用状压DP求解

直接从一道题目入手

[WC2008]游览计划

链接

这应该算是斯坦纳树的板子题了

我们令$f[i][sta]$表示$i$号节点,与其他节点的联通性为$sta$时的最小代价,这里的$sta$是一个二进制数,在它二进制下的每一位中,$0$表示不连通,$1$表示联通

那么转移的时候会有两种情况

  • 由子集转移而来

方程为$$f[i][sta] = \min_{s \in sta}\{f[i][s] + f[i][\complement_ssta] - val[i]\}$$

后面的减是防止加重

这里在枚举子集的时候有一个技巧

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

这样可以枚举出sta的所有子集

  • 由不含该节点的状态转移而来

 转移方程为

其中$i$为新加入的节点

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

大家看到这个方程有没有一种很熟悉的感觉?

是不是很像三角形不等式?

因此,我们可以用SPFA进行这种转移

完整代码

// luogu-judger-enable-o2
// luogu-judger-enable-o2
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
const int limit = 1050;
const int INF = 1e9;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') {x = x * 10 + c - '0'; c = getchar();}
    return x * f;
}
#define MP(i,j) make_pair(i,j)
#define se second
#define fi first
#define Pair pair<int,int>
int N, M, tot = 0;
int a[12][12], f[12][12][limit];
int xx[5] = {-1, +1, 0, 0};
int yy[5] = {0, 0, -1, +1};
int vis[12][12];
struct PRE {
    int x, y, S;
}Pre[12][12][limit];
queue<Pair>q;
void SPFA(int cur) {
    while(q.size() != 0) {
        Pair p = q.front();q.pop();
        vis[p.fi][p.se] = 0;
        for(int i = 0; i <4; i++) {
            int wx = p.fi + xx[i], wy = p.se + yy[i];
            if(wx < 1 || wx > N || wy < 1 || wy > M) continue;
            if(f[wx][wy][cur] > f[p.fi][p.se][cur] + a[wx][wy]) {
                f[wx][wy][cur] = f[p.fi][p.se][cur] + a[wx][wy];
                Pre[wx][wy][cur] = (PRE){p.fi, p.se, cur};
                if(!vis[wx][wy])
                    vis[wx][wy] = 1, q.push(MP(wx,wy));
            }
        }
    }
}
void dfs(int x, int y, int now) {
    vis[x][y] = 1;
    PRE tmp = Pre[x][y][now];
    if(tmp.x == 0 && tmp.y == 0) return;
    dfs(tmp.x, tmp.y, tmp.S);
    if(tmp.x == x && tmp.y == y) dfs(tmp.x, tmp.y, now - tmp.S);
}
int main() {
    //freopen("a.in", "r", stdin);
    N = read(); M = read();
    memset(f, 0x3f, sizeof(f));
    for(int i = 1; i <= N; i++)
        for(int j = 1; j <= M; j++) {
            a[i][j] = read();
            if(a[i][j] == 0)
                f[i][j][1 << tot] = 0, tot++;
        }
    int limit = (1 << tot) - 1;
    for(int sta = 0; sta <= limit; sta++) {
        for(int i = 1; i<= N; i++)
            for(int j = 1; j <= M;j++) {
                for(int s = sta; s; s = (s - 1) & sta) {
                    if(f[i][j][s] + f[i][j][sta - s] - a[i][j] < f[i][j][sta])
                        f[i][j][sta] = f[i][j][s] + f[i][j][sta - s] - a[i][j],
                        Pre[i][j][sta] = (PRE){i,j,s};
                }
                if(f[i][j][sta] < INF) q.push(MP(i,j)), vis[i][j] = 1;
            }
        SPFA(sta);
    }
    int ansx, ansy, flag = 0;
    for(int i = 1; i <= N && !flag; i++)
        for(int j = 1; j <= M; j++)
            if(!a[i][j]) 
                {ansx = i, ansy = j; flag = 1; break;}
    printf("%d\n",f[ansx][ansy][limit]); 
    memset(vis, 0, sizeof(vis));
    dfs(ansx, ansy, limit);
    for(int i = 1; i <= N; i++, puts("")) {
        for(int j = 1; j <= M; j++) {
            if(a[i][j] == 0) putchar('x');
            else if(vis[i][j]) putchar('o');
            else putchar('_');            
        } 
    } 
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏瓜大三哥

视频压缩编码技术(H.264) 之哈夫曼编码

第二步,将两个最小概率组成一组,划成2 个分支域,并标以0 和1;再把2 个分支域合并成1个支域,标以两个概率之和;

1192
来自专栏人工智能LeadAI

Tensorflow动态seq2seq使用总结

tf-seq2seq是Tensorflow的通用编码器 - 解码器框架,可用于机器翻译,文本汇总,会话建模,图像字幕等。 动机 其实差不多半年之前就想吐槽Ten...

9739
来自专栏TensorFlow从0到N

TensorFlow从1到2 - 5 - 非专家莫入!TensorFlow实现CNN

当看到本篇时,根据TensorFlow官方标准《Deep MNIST for Experts》,你已经达到Expert Level,要恭喜了。 且不说是否夸大...

1.5K9
来自专栏mwangblog

开始使用Octave

2214
来自专栏开心的学习之路

神经网络体系搭建(四)——快速上手TensorFlow

本篇是神经网络体系搭建的第四篇,解决体系搭建的TensorFlow相关问题,详见神经网络体系搭建(序) ? TensorFlow安装 建议用Anacond...

3455
来自专栏机器之心

教程 | 经典必读:门控循环单元(GRU)的基本概念与原理

4887
来自专栏简书专栏

基于tensorflow+CNN的垃圾邮件文本分类

tensorflow是谷歌google的深度学习框架,tensor中文叫做张量,flow叫做流。 CNN是convolutional neural netwo...

5413
来自专栏落影的专栏

Metal入门教程(六)边界检测

Metal入门教程(一)图片绘制 Metal入门教程(二)三维变换 Metal入门教程(三)摄像头采集渲染 Metal入门教程(四)灰度计算 Metal入门教程...

3129
来自专栏懒人开发

(1)James Stewart Calculus 5th Edition:Functions and Models

1463
来自专栏Fish

TensorFlow编程入门(一)

写在最前 深度学习辣么火,感觉应该学习学习以免以后人家讲座什么的听不懂。因此想要从应用层面出发,学习学习,那就看看怎么用tensorflow(以下简称tf)做神...

1926

扫码关注云+社区

领取腾讯云代金券