[bzoj4006][斯坦纳树][DP]管道连接

本文主要是介绍[bzoj4006][斯坦纳树][DP]管道连接，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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。

题解

不考虑频道的情况显然是一个斯坦纳树
考虑的话就先做一遍斯坦纳树
求出一个$sum[i]$表示$i$状态下的点联通最小需要多少花费
然后设一个$f[i]$表示$i$状态下的所有点都被选好了的最小花费
枚举一下子集转移就好了
可以预处理一个$ok[i]$表示$i$状态下的这些点能不能合法存在于同一个斯坦纳树中

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#include<ctime>
#include<map>
#include<bitset>
#include<set>
#define LL long long
#define mp(x,y) make_pair(x,y)
#define pll pair<long long,long long>
#define pii pair<int,int>
using namespace std;
inline int read()
{int f=1,x=0;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;
}
int stack[20];
inline void write(LL x)
{if(x<0){putchar('-');x=-x;}if(!x){putchar('0');return;}int top=0;while(x)stack[++top]=x%10,x/=10;while(top)putchar(stack[top--]+'0');
}
inline void pr1(int x){write(x);putchar(' ');}
inline void pr2(LL x){write(x);putchar('\n');}
const int MAXMASK=(1<<10);
const int MAXN=1005;
const int MAXM=3005;
struct node{int x,y,c,next;}a[2*MAXM];int len,last[MAXN];
void ins(int x,int y,int c){len++;a[len].x=x;a[len].y=y;a[len].c=c;a[len].next=last[x];last[x]=len;}queue<int> li;
bool v[MAXN];
int dp[MAXN][MAXMASK];
void spfa(int S)
{while(!li.empty()){int x=li.front();li.pop();v[x]=false;for(int k=last[x];k;k=a[k].next){int y=a[k].y;if(dp[y][S]>dp[x][S]+a[k].c){dp[y][S]=dp[x][S]+a[k].c;if(!v[y])v[y]=true,li.push(y);}}}
}
int bin[25],n,m,P;
int u1[MAXN],u2[MAXN];
void go()
{memset(dp,63,sizeof(dp));int inf=dp[0][0];for(int i=1;i<=P;i++)dp[u2[i]][bin[i]]=0;for(int S=1;S<bin[P+1];S++){for(int i=1;i<=n;i++){for(int j=(S-1)&S;j;j=(j-1)&S)dp[i][S]=min(dp[i][S],dp[i][j]+dp[i][S^j]);if(dp[i][S]!=inf)v[i]=true,li.push(i);}spfa(S);}
}
int sum[MAXMASK];
int num[15],ok[MAXMASK];
int f[MAXMASK];
int main()
{
//	freopen("1.in","r",stdin);bin[1]=1;for(int i=2;i<=20;i++)bin[i]=bin[i-1]<<1;n=read();m=read();P=read();for(int i=1;i<=m;i++){int x=read(),y=read(),c=read();ins(x,y,c);ins(y,x,c);}for(int i=1;i<=P;i++){u1[i]=read(),u2[i]=read();num[u1[i]]|=bin[i];}for(int i=0;i<bin[P+1];i++){ok[i]=1;for(int j=1;j<=P;j++)if(i&bin[j]){if((i&num[u1[j]])!=num[u1[j]]){ok[i]=0;break;}}}go();memset(sum,63,sizeof(sum));for(int i=0;i<bin[P+1];i++)for(int j=1;j<=n;j++)sum[i]=min(sum[i],dp[j][i]);memset(f,63,sizeof(f));f[0]=0;for(int i=1;i<bin[P+1];i++){if(ok[i])f[i]=min(f[i],sum[i]);for(int j=(i-1)&i;j;j=(j-1)&i)if(ok[j])f[i]=min(f[i],sum[j]+f[i^j]);}pr2(f[bin[P+1]-1]);return 0;
}

这篇关于[bzoj4006][斯坦纳树][DP]管道连接的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---