\(\mathbf{POJ\;2432}\)题解

题意

给出圆上的\(N\)个点，每个点有一个经度（大于\(0\)小于\(360\)）；再给出\(M\)条双向边，保证边\(x y\)仅会沿圆上较短的弧连接，且不存在边连接圆上相对的两个点的情况。

求一条从点\(1\)出发最后回到点\(1\)，且能环绕圆的经过点数最少的路径。

思路

边权为\(1\)的最短路，显然可以想到BFS。但由于还要满足“能环绕圆”这一条件，我们需要加一些限制。

不妨预处理出每条边的连接的两地间的经度差作为边权，顺时针边置正权，逆时针边置负权，并在BFS的状态中加入一维，表示路径权值和。

那么在BFS时，就可以用已走过的路径权值和\(dis\)来判断一条从\(1\)出发再回到\(1\)的路径是否合法了。

不难发现，若\(dis\)不为\(0\)，那么一条从\(1\)出发回到\(1\)的路径一定是合法的，反之亦然。

另外，一个状态\(f(x,dis)\)一定不会出现两次，所以用一个集合（STL set）来记录已经出现过的状态，起一般BFS中标记数组的作用。

最后，在计算答案时用一个成员变量\(step\)记录经过了几个点。

使用以上算法即可通过本题。如果想进一步优化，可以把queue改为手写queue，set改为手写Hash。

代码

#include<iostream>

#include<algorithm>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

//include STL queue

#include<queue>

//include STL set

#include<set>

//include STL pair

#include<utility>

#define N 5005

#define M 25005

using namespace std;

struct pos{

	int x,dis;

	int step;

}tmp,fro;

struct Edge{

	int nxt,to,w;

}e[M<<1];

int n,m,tot=1,head[N],a[N];

queue<pos>q;

set<pair<int,int> >cnt;

void addedge(int x,int y,int z)

{

	e[++tot]=(Edge){head[x],y,z},head[x]=tot;//顺时针

	e[++tot]=(Edge){head[y],x,-z},head[y]=tot;//逆时针

}

int getdis(int x,int y)//返回两地经度差

{

	int z=min(abs(x-y),360-abs(x-y));

	if((x+z)%360==y)

		return z;//顺时针

	else

		return -z;//逆时针

}

int bfs()

{

	fro.x=1;fro.dis=0,fro.step=0;

	q.push(fro);

	while(!q.empty())

	{

		fro=q.front(),q.pop();

		int x=fro.x,dis=fro.dis,step=fro.step;

		cnt.insert(make_pair(x,dis));

		for(int i=head[x],y;i;i=e[i].nxt)

		{

			y=e[i].to;

			if(y==1 && dis+e[i].w)

				return step+1;

			if(cnt.find(make_pair(y,dis+e[i].w))!=cnt.end())

				continue;

			tmp.x=y,tmp.dis=dis+e[i].w,tmp.step=step+1;

			q.push(tmp);

		}

	}

	return -1;

}

int main()

{

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

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

		scanf("%d",a+i);

	for(int i=1,x,y,z;i<=m;i++){

		scanf("%d%d",&x,&y);

		z=getdis(a[x],a[y]);

		if(z>0)	addedge(x,y,z);//顺时针

		else	addedge(y,x,-z);//逆时针

	}

	printf("%d\n",bfs());

	return 0;

}

/*

3 3

0

120

240

1 2

2 3

1 3

*/

完结撒花

巴特西

POJ 2432

\(\mathbf{POJ\;2432}\)题解

题意

思路

代码

最新文章

热门文章