题目

描述

（样例都懒得发出来了）

题目大意

给你一个有向图，从111号点出发，绕一圈回来。这一圈中必须经过222号点。

问经过的最少的点数（不重复）。

思考历程

一看就觉得是一道神题。

然后仔细观察一下数据范围：范围好像很小似的。

于是我就果断地想到了网络流！

于是我拼命地往网络流的方向去想，可是最后还是没有出什么结果。

看着比赛即将结束，也不应该不拿分，于是打暴力！

然后我就很自然地打了个IDA*

枚举答案ansansans，由于每个点最多经过两次，222号点只会经过一次，那么路径的长度不大于2∗ans−12*ans-12∗ans−1

预处理两点间距离，于是估价函数就显而易见了。

结果……

啊？AC了！！！

数据真水啊！

正解

这题实际上是强大的DP做法。

设fi,jf_{i,j}fi,j表示走路径j→1→ij \to 1 \to ij→1→i，所经过的最少的城市数目。

转移的时候就通过分别从两边延伸出去。

还有另外一条方程：fi,j←fj,i+dis(j,i)−1 (i≠j)f_{i,j} \leftarrow f_{j,i}+dis(j,i)-1\ \ (i\neq j)fi,j←fj,i+dis(j,i)−1 (i̸=j)

fj,if_{j,i}fj,i可以理解成路径i→1→ji\to 1\to ji→1→j，加上dis(j,i)dis(j,i)dis(j,i)之后就变成j→i→1→j→ij \to i \to 1 \to j \to ij→i→1→j→i（重复的不计）

相当于在现在的路径上添个环。

于是这个DP就有些神仙了。判重呢？怎么就没有判重了！

首先很容易证明不存在j→1→k→k→ij \to 1 \to k \to k \to ij→1→k→k→i这样的情况，因为这样显然不是最优的，一定会被覆盖。

那会不会出现点数算重复了的状况呢？对于这点，我的理解比较感性：一个点最多出现在路径中两次。其实路径可以看成一堆环拼在一起，这个出现两次的点能与111点形成一个环。上面的这条方程式就是应对这种状况。在计算的过程中，的确有可能出现算重的状况，总会出现一个正确的没有算重的状况，而这个正确的状况就会将它们所覆盖。

然后这个DP就好像是正确的了。

由于这个东西明显有后效性，所以用Dijsktra来转移就可以了。

还有一种方法是题解的（我没有打），也是DP。

设fi,jf_{i,j}fi,j表示路径1→i→j→11 \to i \to j \to 11→i→j→1经过最小点数。

转移：fx,y←fi,j+dis(j,x)+dis(x,y)+dis(y,i)−1f_{x,y} \leftarrow f_{i,j}+dis(j,x)+dis(x,y)+dis(y,i)-1fx,y←fi,j+dis(j,x)+dis(x,y)+dis(y,i)−1

这个方程其实比较好懂，不就是在i→ji\to ji→j这一段上强安上一个环嘛！

用类似上面的思想来分析，这个也是对的。

就理解成用将一堆环连在一起。

当然，由于这题的垃圾数据，其它方法过的也有很多。

好好打暴力就也可以过……

代码

using namespace std;

#include <cstdio>

#include <cstring>

#include <algorithm>

inline bool getmin(int &a,int b){return a>b?a=b:0;}

#define N 110

#define M 210

int n,m;

bool e[N][N];

int dis[N][N];

int f[N][N];

struct Node{

	int x,y,s;

} h[1000001];

int nh;

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

	return son.s>fa.s;

}

int main(){

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

	memset(dis,63,sizeof dis);

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

		int u,v;

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

		u--,v--;

		dis[u][v]=e[u][v]=1;

 	}

 	for (int k=0;k<n;++k)

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

 			for (int j=0;j<n;++j)

 				dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);

	memset(f,63,sizeof f);

	f[0][0]=1;

	h[nh++]={0,0,1};

	while (nh){

		Node top=h[0];

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

		if (f[top.x][top.y]<top.s)

			continue;

		if (top.x!=top.y)

			getmin(f[top.x][top.y],f[top.y][top.x]+dis[top.y][top.x]-1);

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

			if (e[top.x][i] && getmin(f[i][top.y],f[top.x][top.y]+(i!=top.y))){

				h[nh]={i,top.y,f[i][top.y]};

				push_heap(h,h+ ++nh,cmph);

			}

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

			if (e[i][top.y] && getmin(f[top.x][i],f[top.x][top.y]+(i!=top.x))){

				h[nh]={top.x,i,f[top.x][i]};

				push_heap(h,h+ ++nh,cmph);

			}

	}

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

	return 0;

}

这题的代码是没有必要注解的，isn’t it?

总结

有时候我们会遇到一些需要判重的题目。

如果暴力方法时间复杂度超标，那我们可以考虑其他的思路。

想一想有没有什么方法可以在局部去重，并且计算准确的答案。

让这个答案覆盖掉其它不合法的东西。

巴特西

[JZOJ3177] 【GDOI2013模拟5】安全监控

题目

描述

题目大意

思考历程

正解

代码

总结

最新文章

热门文章