BZOJ4006: [JLOI2015]管道连接(斯坦纳树,状压DP)

Time Limit: 30 Sec  Memory Limit: 128 MB

Submit: 1171  Solved: 639

[Submit][Status][Discuss]

Description

小铭铭最近进入了某情报部门,该部门正在被如何建立安全的通道连接困扰。

该部门有 n 个情报站,用 1 到 n 的整数编号。给出 m 对情报站 ui;vi 和费用 wi,表示情

报站 ui 和 vi 之间可以花费 wi 单位资源建立通道。

如果一个情报站经过若干个建立好的通道可以到达另外一个情报站,那么这两个情报站就

建立了通道连接。形式化地,若 ui 和 vi 建立了通道,那么它们建立了通道连接;若 ui 和 vi 均

与 ti 建立了通道连接,那么 ui 和 vi 也建立了通道连接。

现在在所有的情报站中,有 p 个重要情报站,其中每个情报站有一个特定的频道。小铭铭

面临的问题是,需要花费最少的资源,使得任意相同频道的情报站之间都建立通道连接。

Input

第一行包含三个整数 n;m;p,表示情报站的数量,可以建立的通道数量和重要情报站的数

量。接下来 m 行,每行包含三个整数 ui;vi;wi,表示可以建立的通道。最后有 p 行,每行包含

两个整数 ci;di,表示重要情报站的频道和情报站的编号。

Output

输出一行一个整数,表示任意相同频道的情报站之间都建立通道连接所花费的最少资源总量。

Sample Input

5 8 4 1 2 3 1 3 2 1 5 1 2 4 2 2 5 1 3 4 3 3 5 1 4 5 1 1 1 1 2 2 3 2 4

Sample Output

4

HINT

选择 (1; 5); (3; 5); (2; 5); (4; 5) 这 4 对情报站连接。

对于 100% 的数据,0 <ci <= p <= 10; 0 <ui;vi;di <= n <= 1000; 0 <= m <= 3000; 0 <= wi <=

20000。

Source

斯坦纳森林

设$f[i][sta]$表示$i$号节点,与关键节点的联通性为$sta$时的最小值

假设我们已经求出了$f$

那么我们令$g[sta]$表示,颜色联通性为$sta$时的最小值

$g$比较好求,枚举子集转移就可以

$f$的话,如果学过斯坦纳树也比较好求

按照套路,两种转移方法,一种是枚举子集,一种是SPFA

#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
const int MAXN = 1e6 + 10;
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;
}
int N, M, P;
struct node {
    int u, v, w, nxt;
}E[MAXN];
int head[MAXN], num = 1;
inline void AddEdge(int x, int y,int z) {
    E[num].u = x; E[num].v = y; E[num].w = z;
    E[num].nxt = head[x]; head[x] = num++;
}
struct Point {
    int color, ID;
}a[MAXN];
int f[1051][1051], g[1051];
int vis[MAXN], sum[MAXN];
queue<int>q;
void SPFA(int now) {
    while(q.size() != 0) {
        int p = q.front(); q.pop(); vis[p] = 0;
        for(int i = head[p]; i != -1; i = E[i].nxt) {
            int v = E[i].v;
            if(f[v][now] > f[p][now] + E[i].w) {
                f[v][now] = f[p][now] + E[i].w;
                if(!vis[v]) vis[v] = 1, q.push(v);
            }
        }
    }
}
int tmp[11];
bool check(int sta) {
    memset(tmp, 0, sizeof(tmp));
    for(int i = 1; i <= 10; i++)
        if(sta & (1 << i - 1)) tmp[a[i].color]++;
    for(int i = 1; i <= 10; i++)
        if(tmp[i] && tmp[i] != sum[i]) return 0;
    return 1;
}
int main() {
    #ifdef WIN32
    freopen("a.in", "r", stdin);
    #endif
    memset(head, -1, sizeof(head));
    N = read(), M = read(), P = read();
    for(int i = 1; i <= M; i++) {
        int x = read(), y = read(), z = read();
        AddEdge(x, y, z);AddEdge(y, x, z);
    }
    memset(f, 0x3f, sizeof(f));
    memset(g, 0x3f, sizeof(g));
    for(int i = 1; i <= P; i++) 
        a[i].color = read(), a[i].ID = read(), sum[a[i].color]++,f[a[i].ID][1 << (i - 1)] = 0;        
    int limit = (1 << P) - 1;    
    for(int sta = 0; sta <= limit; sta++) {
        for(int i = 1; i <= N; i++) {
            for(int S = sta; S; S = (S - 1) & sta) 
                f[i][sta] = min(f[i][sta], f[i][S] + f[i][sta - S]);
            q.push(i),vis[i] = 1;
        }
        SPFA(sta);    
    }
    for(int sta = 0; sta <= limit; sta++) 
        for(int i = 1; i <= N; i++)
            g[sta] = min(g[sta], f[i][sta]);
    for(int sta = 0; sta <= limit; sta++)
        if(check(sta))
            for(int S = sta; S; S = (S - 1) & sta)
                if(check(S))
                    g[sta] = min(g[sta], g[S] + g[sta - S]);
    printf("%d", g[(1 << P) - 1]);
    return 0;
}

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏CSDN技术头条

使用hadoop进行大规模数据的全局排序

1. Hellow hadoop~~! Hadoop(某人儿子的一只虚拟大象的名字)是一个复杂到极致,又简单到极致的东西。 说它复杂,是因为一个hadoop...

37050
来自专栏生信宝典

R包reshape2,轻松实现长、宽数据表格转换

本文翻译自外文博客,原文链接:https://seananderson.ca/2013/10/19/reshape/

29620
来自专栏数据结构与算法

1010 过河卒

1010 过河卒 2002年NOIP全国联赛普及组  时间限制: 1 s  空间限制: 128000 KB  题目等级 : 黄金 Gold 题解  查看运行结果...

29050
来自专栏新智元

手把手教你如何用Julia做GPU编程(附代码)

GPU是一个大规模并行处理器,具有几千个并行处理单元。 例如,本文中使用的Tesla k80提供4992个并行CUDA内核。 GPU在频率,延迟和硬件功能方面与...

36510
来自专栏机器之心

教程 | 如何在Python中快速进行语料库搜索:近似最近邻算法

39040
来自专栏老秦求学

算法一之N皇后问题

(写这篇文章主要是明天就要考试了,算法考试,今天不想再复习了,xiang着今天也开通了博客,于是在这个平台上进行复习,应该会更高效。最后祝愿我明天考个好成绩。嘻...

399100
来自专栏天天P图攻城狮

OpenGL shader性能优化策略(一):减少分支语句

一、优化策略:减少使用分支语句 在编写OpenGL shader时,一定要注意减少使用if或for语句,因为这些语句引入分支、会大大降低shader的性能,...

93420
来自专栏数据分析

[数据清洗]-Pandas 清洗“脏”数据(一)

概要 准备工作 检查数据 处理缺失数据 添加默认值 删除不完整的行 删除不完整的列 规范化数据类型 必要的转换 ...

1.1K70
来自专栏PPV课数据科学社区

【学习】使用hadoop进行大规模数据的全局排序

1. Hellow hadoop~~! Hadoop(某人儿子的一只虚拟大象的名字)是一个复杂到极致,又简单到极致的东西。 说它复杂,是因为一个hadoop...

31130
来自专栏人工智能LeadAI

拼图游戏和它的AI算法

写了个拼图游戏,探讨一下相关的AI算法。拼图游戏的复原问题也叫做N数码问题。 拼图游戏 N数码问题 广度优先搜索 双向广度优先搜索 A*搜索 游戏设定 实现一个...

645110

扫码关注云+社区

领取腾讯云代金券