题目描述

小铭铭最近进入了某情报部门，该部门正在被如何建立安全的通道连接困扰。该部门有 n 个情报站，用 1 到 n 的整数编号。给出 m 对情报站 ui;vi 和费用 wi，表示情报站 ui 和 vi 之间可以花费 wi 单位资源建立通道。

如果一个情报站经过若干个建立好的通道可以到达另外一个情报站，那么这两个情报站就建立了通道连接。形式化地，若 ui 和 vi 建立了通道，那么它们建立了通道连接；若 ui 和 vi 均与 ti 建立了通道连接，那么 ui 和 vi 也建立了通道连接。

现在在所有的情报站中，有 p 个重要情报站，其中每个情报站有一个特定的频道。小铭铭面临的问题是，需要花费最少的资源，使得任意相同频道的情报站之间都建立通道连接。

Sol

首先要会斯坦那树。

其实只是一种解决一类状压dp的方法。

当我们需要进行有关联通性的状压 dp 时 , 只要求关键点连通且关键点较少 , 但是非关键点比较多的时候 , 可以用到斯坦那树。

其实是一类不要求所有点连通而只要求一部分点连通的 \(MST\) , 只能状压来求。

状压关键点的连通性 , 并确定一个点已经在树中 , 那么在不影响关键点的状态 , 也就是相同状态中可以用最短路来转移 , 而不同状态一般固定一个点 , 枚举子集然后合并。

通过最短路巧妙解决了非关键之间连边的决策。

但是这道题并不是要求所有关键点联通 , 而是要一些类关键点分别连通 , 不过这个也简单 , 我们最后状压一下所有种类之间的连通性再做一遍背包就行了。

我的代码常数太大,必须要开 O2 才能过..

code:

#include<bits/stdc++.h>

using namespace std;

#define Set(a,b) memset(a,b,sizeof(a))

template<class T>inline void init(T&x){

	x=0;char ch=getchar();bool t=0;

	for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') ch=getchar();

	for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<1)+(x<<3)+(ch-48);

	if(t) x=-x;return ;

}

const int N=1021,M=3021;

const int MAXN=1<<10;

const int INF=2e9;

const int NN=13;

typedef long long ll;

struct pack{

	int u,val;

	pack(int _u=0,int _val=0){u=_u,val=_val;}

	inline bool operator <(const pack B)const{

		return val>B.val;

	}

}Im[NN];

queue<int> Q;

bool vis[N];

int n,m,p;

struct edge{int to,next,w;}a[M<<1];

int head[N],cnt=0;

inline void add(int x,int y,int w){a[++cnt]=(edge){y,head[x],w};head[x]=cnt;}

int dis[N][MAXN],g[MAXN];

int id[N];

inline void SPFA(int S){

	while(!Q.empty()){

		int u=Q.front();Q.pop();

		for(int v,i=head[u];i;i=a[i].next){

			v=a[i].to;

			if(dis[v][S]==-1||dis[v][S]>dis[u][S]+a[i].w) {

				dis[v][S]=dis[u][S]+a[i].w;

				if(!vis[v]) Q.push(v),vis[v]=1;

			}

		}

		vis[u]=0;

	}

	return;

}

int size[NN],R[NN],h=0,ful[NN];

inline int Calc(int S){int sta=0;for(int i=0;i<h;++i) if((S&ful[i])==ful[i]) sta|=1<<i;return sta;}

int main()

{

	init(n),init(m),init(p);

	int u,v,w;

	for(int i=1;i<=m;++i) {

		init(u),init(v),init(w);

		add(u,v,w);add(v,u,w);

	}

	Set(id,-1);Set(dis,-1);

	for(int i=1;i<=p;++i) {

		init(w),init(u);

		Im[i]=pack(u,w);

	}sort(Im+1,Im+1+p);

	int pre=0;int now=0;

	for(int i=1;i<=p;++i) {

		id[Im[i].u]=i-1;

		if(Im[i].val!=Im[i+1].val) {

			R[h]=i;size[h]=i-pre;

			ful[h]=((1<<i)-1)^now;now|=ful[h];

			pre=i;++h;

		}

	}

	for(int i=1;i<=n;++i) {if(~id[i]) dis[i][1<<id[i]]=0;dis[i][0]=0;}

	int Full=(1<<p)-1;Set(g,-1);

	for(int S=0;S<=Full;++S){

		int sta=Calc(S);

		for(int i=1;i<=n;++i) {

			vis[i]=0;

			for(int T=(S-1)&S;T>0;T=(T-1)&S){

				if(T<=0) break;

				if((~dis[i][T])&&(~dis[i][S^T])) {if(dis[i][S]==-1||dis[i][S]>dis[i][T]+dis[i][S^T]) dis[i][S]=dis[i][T]+dis[i][S^T];}

			}

			if(dis[i][S]!=-1) {

				Q.push(i);vis[i]=1;

				if((g[sta]==-1||g[sta]>dis[i][S])) g[sta]=dis[i][S];

			}

		}SPFA(S);

	}int full=(1<<h)-1;

	for(int S=0;S<=full;++S){

		for(int T=(S-1)&S;T>0;T=(T-1)&S){

			if(T<=0) break;if(g[T]==-1||g[S^T]==-1) continue;

			if(g[S]==-1||g[S]>g[T]+g[S^T]) g[S]=g[T]+g[T^S];

		}

	}

	cout<<g[full]<<endl;

}

巴特西

【LuoguP3264】[JLOI2015] 管道连接(斯坦那树)

题目描述

Sol

最新文章

热门文章