[JLOI2015]管道连接（斯坦纳树）

[Luogu3264]

原题解

多个频道,每个频道的关键点要求相互联通

详见代码,非常巧妙

#include<cstdio>

#include<iostream>

#include<cstring>

#include<algorithm>

#include<queue>

#define debug(...) fprintf(stderr,__VA_ARGS__)

#define Debug(x) cout<<#x<<"="<<x<<endl

using namespace std;

typedef long long LL;

const int INF=1e9+7;

inline LL read(){

	register LL x=0,f=1;register char c=getchar();

	while(c<48||c>57){if(c=='-')f=-1;c=getchar();}

	while(c>=48&&c<=57)x=(x<<3)+(x<<1)+(c&15),c=getchar();

	return f*x;

}

const int MAXN=1005;

const int MAXM=6005;

const int MAXL=1<<10;

struct Edge{

	int v,w,c,next;

}e[MAXM];

int first[MAXN],Ecnt=1;

inline void Add_edge(int u,int v,int w=0,int c=0){

	e[++Ecnt]=(Edge){v,w,c,first[u]};

	first[u]=Ecnt;

}

struct Point{

	int col,id;

	inline friend bool operator < (Point a,Point b){

		return a.col<b.col;

	}

}a[12];

int f[MAXN][MAXL],g[MAXL];

bool inq[MAXN];

int n,m,K,Cnt;

queue <int> q;

inline void SPFA(int sta){

	while(!q.empty()){

		int u=q.front();q.pop();inq[u]=false;

		for(int i=first[u];i;i=e[i].next){

			int v=e[i].v,w=e[i].w;

			if(f[u][sta]+w<f[v][sta]){

				f[v][sta]=f[u][sta]+w;

				if(!inq[v]) inq[v]=true,q.push(v);

			}

		}

	}

}

inline int solve(int cnt){//一共只要考虑cnt个点

	for(int i=1;i<(1<<cnt);i++){//这一维为基础:状态

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

			for(int k=(i-1)&i;k;k=(k-1)&i)

				f[j][i]=min(f[j][i],f[j][k]+f[j][i^k]);//再枚举j:以j为根连接状态了j的点

			if(f[j][i]<f[0][0])

				inq[j]=1,q.push(j);

		}

		SPFA(i);//我理解为暴力散开

	}

	int res=INF;

	for(int i=1;i<=n;i++) res=min(res,f[i][(1<<cnt)-1]);

	return res;

}

int main(){

	n=read(),m=read(),K=read();

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

		int x=read(),y=read(),w=read();

		Add_edge(x,y,w);

		Add_edge(y,x,w);

	}

	for(int i=1;i<=K;i++)

		a[i].col=read(),a[i].id=read();

	sort(a+1,a+K+1);

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

		if(a[i].col!=a[i-1].col) Cnt++;

		a[i].col=Cnt;//离散化

	}

	Cnt=1<<Cnt;

	memset(g,0x3f,sizeof g);

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

		memset(f,0x3f,sizeof f);

		int tmp=0;

		for(int j=1;j<=K;j++){

			if((1<<(a[j].col-1))&i)

				f[a[j].id][1<<tmp++]=0;//i这些频道共有tmp个点

		}

		g[i]=solve(tmp);//i这些频道 <- 考虑这tmp个点的答案

	}

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

		for(int j=(i-1)&i;j;j=(j-1)&i)

			g[i]=min(g[i],g[j]+g[i^j]);//再更新一次

	}

	printf("%d\n",g[Cnt-1]);

}