题目

题目大意

给你一个图，让你选择权值和最小的边，使得\(1\)和\(n\)，\(2\)和\(n-1\)，……，\(K\)和\(n-K+1\)联通。

\(K\leq 4\)

思考历程

一看到这题就觉得特别神仙……

然后去思考网络流……

搞出了一个最小割，后来发现这是错的……

匆匆打了个表，获得了这题的十分之一的分数。

正解

其实这题有水法，许多人是全排列+\(SPFA\)，跑了一遍之后将路过的边清\(0\)，继续跑。这样贪心显然是错的，反例也有，但是极其水的数据居然给了他们\(100\)分！

正解是DP。

题解中有个叫做\(stenir \ tree\)的东西，感觉似乎很强大。当然我不懂，我只会DP。

现在我们是要求出一个最小生成森林，使得一些点对联通。

考虑一棵树。显然，树的叶子节点一定是要求联通的节点（反过来倒不一定）。

于是我们就试着DP……

设\(f_{S,i}\)表示当前这棵树的根节点为\(i\)，并且\(S\)集合中的所有点连在了一起的最小代价

转移的时候就是两棵树的根节点连在一起，也就是\(f_{S',i}+w(i,j)+f_{S-S',j}\to f_{S,i}\)

\(S'\)是\(S\)的子集。（枚举\(S\)和\(S'\)的时间复杂度是\(3^k\)的，\(k\)表示位数，具体实现比较巧妙，见代码）

然后这道题就差不多完了。注意，转移的时候一般是\(S\)从低到高转移，但也会向\(S\)相等的状态转移，这就意味着会有后效性。所以，对于同层的转移，我们特殊地用最短路算法来处理。

代码

using namespace std;

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <climits>

inline void update(int &a,int b){a>b?a=b:0;}

#define N 10010

#define M 10010

int n,m,K;

struct EDGE{

	int to,len;

	EDGE *las;

} e[M*2];

int ne;

EDGE *last[N];

inline void link(int u,int v,int len){

	e[ne]={v,len,last[u]};

	last[u]=e+ne++;

}

int f[256][N],*dis;

struct Node{

	int x,dis;

} h[1000001];

int nh;

inline bool cmph(const Node &son,const Node &fa){

	return son.dis>fa.dis;

}

int mn[256],ans[256];

inline bool ok(int s){

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

		if ((s>>i&1)^(s>>i+K&1))

			return 0;

	return 1;

}

int main(){

	freopen("in.txt","r",stdin);

	scanf("%d%d%d",&n,&m,&K);

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

		int u,v,len;

		scanf("%d%d%d",&u,&v,&len);

		link(u,v,len),link(v,u,len);

	}

	memset(f,63,sizeof f);

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

		f[1<<i-1][i]=f[1<<K+i-1][n-i+1]=0;

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

		f[0][i]=0;

	for (int s=1;s<1<<K*2;++s){

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

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

				if (f[s1][i]<0x3f3f3f3f)

					for (EDGE *ei=last[i];ei;ei=ei->las)

						update(f[s][i],f[s1][i]+ei->len+f[s-s1][ei->to]);

		dis=f[s];

		nh=0;

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

			h[nh++]={i,dis[i]};

		while (nh){

			int x=h[0].x,disx=h[0].dis;

			pop_heap(h,h+nh--,cmph);

			if (disx>dis[x])

				continue;

			for (EDGE *ei=last[x];ei;ei=ei->las)

				if (disx+ei->len<dis[ei->to]){

					dis[ei->to]=disx+ei->len;

					h[nh++]={ei->to,dis[ei->to]};

					push_heap(h,h+nh,cmph);

				}

		}

		mn[s]=INT_MAX;

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

			update(mn[s],dis[i]);

	}

	memset(ans,63,sizeof ans);

	ans[0]=0;

	for (int s=1;s<1<<K*2;++s)

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

			if (ok(s-s1) && ok(s1))

				update(ans[s],ans[s-s1]+mn[s1]);

	if (ans[(1<<K*2)-1]<0x3f3f3f3f)

		printf("%d\n",ans[(1<<K*2)-1]);

	else

		printf("-1\n");

	return 0;

}

总结

不是什么题都能用网络流做的……

DP也能玩出各种花样……

巴特西

[JZOJ3400] 【GDOI2014模拟】旅行

题目

题目大意

思考历程

正解

代码

总结

最新文章

热门文章