「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

04-17 12:07