luogu P3264 [JLOI2015]管道连接

LINK：管道连接

一张无向图 有P个关键点 其中有K个集合 各个集合要在图中形成联通块 边有边权 求最小代价。

其实还是生成树问题 某个点要和某个点要在生成树中 类似这个意思。

可以发现 是斯坦纳树问题。但是有些集合是不必要连起来的 我们可以使用子集合并 将一些状态给合并起来。

例如 我们设f[i][s]表示到达某个点形成的位置集合为s的最小代价可以发现s之中全部都是联通的 但是s之中可能可以不连通 但是我们让其强行联通 最后再将联通的状态合并起来 就是答案了。

(说白了其实是进行状态强制合并dp 这个很容易搞 可以直接枚举子集 或者 直接枚举p进行转移会更高效。

真的不作就不会死 spfa 直接秒过 写了个dij上去只有40 开o2才过 果然 稀疏图中spfa跑的超快的好吧 它还没死。

const int MAXN=3010,maxn=11;
int n,m,p,len,l,r;
int s[maxn],id[MAXN],f[MAXN][1<<maxn],vis[MAXN],g[1<<maxn];
int q[MAXN*MAXN];
int lin[MAXN],nex[MAXN<<1],ver[MAXN<<1],e[MAXN<<1];
inline void add(int z,int x,int y)
{
ver[++len]=y;nex[len]=lin[x];lin[x]=len;e[len]=z;
ver[++len]=x;nex[len]=lin[y];lin[y]=len;e[len]=z;
}
inline void spfa(int s)
{
while(++l<=r)
{
int x=q[l];vis[x]=0;
go(x)
{
if(f[tn][s]>f[x][s]+e[i])
{
f[tn][s]=f[x][s]+e[i];
if(!vis[tn])vis[tn]=1,q[++r]=tn;
}
}
}
}
int main()
{
freopen("1.in","r",stdin);
get(n);get(m);get(p);
memset(f,0x3f,sizeof(f));
memset(g,0x3f,sizeof(g));
rep(1,m,i)add(read(),read(),read());
rep(1,p,i)
{
int x,y;
get(x);get(y);
s[x]|=(1<<(i-1));
id[y]=i;f[y][1<<(i-1)]=0;
}
int maxx=(1<<p)-1;
rep(1,maxx,i)
{
l=r=0;
rep(1,n,j)
{
for(int s=i;s;s=i&(s-1))
f[j][i]=min(f[j][i],f[j][s]+f[j][s^i]);
if(f[j][i]<INF)q[++r]=j,vis[j]=1;
g[i]=min(g[i],f[j][i]);
}
spfa(i);
}
rep(1,maxx,i)
{
rep(1,p,j)
{
if(!s[j])continue;
if((i&s[j])!=s[j])continue;
g[i]=min(g[i],g[i^s[j]]+g[s[j]]);
}
}
put(g[maxx]);
return 0;
}