luogu P3264 [JLOI2015]管道连接

一张无向图有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;

}

巴特西

luogu P3264 [JLOI2015]管道连接

最新文章

热门文章