「JLOI2015」管道连接 解题报告

「JLOI2015」管道连接

先按照斯坦纳树求一个

然后合并成斯坦纳森林

直接枚举树的集合再dp一下就好了

---

Code:

#include <cstdio>

#include <cctype>

#include <cstring>

#include <algorithm>

using std::min;

const int N=1<<10;

template <class T>

void read(T &x)

{

	x=0;char c=getchar();

	while(!isdigit(c)) c=getchar();

	while(isdigit(c)) x=x*10+c-'0',c=getchar();

}

int head[N],to[N<<3],Next[N<<3],edge[N<<3],cnt;

void add(int u,int v,int w)

{

    to[++cnt]=v,edge[cnt]=w,Next[cnt]=head[u],head[u]=cnt;

}

int n,m,p,dp[N][N],f[N],yuu[12];

int q[N*N],l,r,vis[N];

void spfa(int s)

{

	while(l<=r)

	{

		int now=q[l++];

		vis[now]=0;

		for(int v,i=head[now];i;i=Next[i])

			if(dp[v=to[i]][s]>dp[now][s]+edge[i])

			{

				dp[v][s]=dp[now][s]+edge[i];

				if(!vis[v]) vis[q[++r]=v]=1;

			}

	}

}

int main()

{

	read(n),read(m),read(p);

	memset(dp,0x3f,sizeof dp);

	memset(f,0x3f,sizeof f);

	for(int u,v,w,i=1;i<=m;i++)

	{

		read(u),read(v),read(w);

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

	}

	for(int c,d,i=1;i<=p;i++)

	{

		read(c),read(d);

		yuu[c]|=1<<i-1;

		dp[d][1<<i-1]=0;

	}

	for(int s=1;s<1<<p;s++)

	{

		l=1,r=0;

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

		{

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

				if(dp[i][s]>dp[i][t]+dp[i][t^s])

					dp[i][s]=dp[i][t]+dp[i][t^s];

			if(dp[i][s]<dp[0][0]) q[++r]=i;

		}

		spfa(s);

		for(int i=1;i<=n;i++) f[s]=min(f[s],dp[i][s]);

	}

	int ct=0;

	while(yuu[ct+1]) ++ct;

	for(int s=1;s<1<<ct;s++)

	{

		int sta=0;

		for(int i=0;i<ct;i++)

			if(s>>i&1)

				sta|=yuu[i+1];

		for(int i=0;i<ct;i++)

			if(s>>i&1)

				f[sta]=min(f[sta],f[sta^yuu[i+1]]+f[yuu[i+1]]);

	}

	printf("%d\n",f[(1<<p)-1]);

	return 0;

}

---

2019.2.26