[NOIp2014] luogu P2296 寻找道路

不知道是因为我菜还是别的，最近老是看错题。

题目描述

在有向图 GGG 中，每条边的长度均为 1，现给定起点和终点，请你在图中找一条从起点到终点的路径，该路径满足以下条件：

路径上的所有点的出边所指向的点都直接或间接与终点连通。
在满足条件 1 的情况下使路径最短。

注意：图 GGG 中可能存在重边和自环，题目保证终点没有出边。

请你输出符合条件的路径的长度。

Solution

定义一个点是黑点，当且仅当它能沿着边走到终点（不需满足题设条件）；
定义一个点是YH点，当且仅当它引出的边指向的点都是黑点（起点终点都是YH点）；
删去所有非YH点，跑 SPFA 即可。

注意反向建图

#include<cstdio>

#include<cstdlib>

#include<cstring>

const int MAXN=10010;

const int MAXM=200010;

struct node{

	int x,y,next;

}e[MAXM];

int len=0;

int first[MAXN];

int n,m;

int sx,sy;

bool dis[MAXN];

int ST,ED;

int st,ed;

int q[MAXM*10];

int f[MAXN],v[MAXN];

void ins(int x,int y){

	e[++len].x=x;e[len].y=y;

	e[len].next=first[x];first[x]=len;

}

void init(){

	memset(dis,1,sizeof(dis));dis[ED]=0;

	st=1;ed=2;q[1]=ED;

	while(st!=ed){

		int x=q[st];

		for(int i=first[x];i;i=e[i].next){

			int y=e[i].y;

			if(!dis[y]) continue;

			dis[y]=0;

			q[ed++]=y;

		}

		++st;

	}

	if(dis[ST]){

		puts("-1");

		exit(0);

	}

	bool rework[MAXN];

	memset(rework,0,sizeof(rework));

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

		if(dis[i]){

			rework[i]=1;

			for(int j=first[i];j;j=e[j].next)

				rework[e[j].y]=1;

		}

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

		dis[i]=rework[i];

}

void spfa(){

	memset(f,63,sizeof(f));f[ED]=0;

	memset(v,0,sizeof(v));v[ED]=1;

	st=1;ed=2;q[1]=ED;

	while(st!=ed){

		int x=q[st];

		for(int i=first[x];i;i=e[i].next){

			int y=e[i].y;

			if(dis[y]) continue;

			if(f[y]>f[x]+1){

				f[y]=f[x]+1;

				if(!v[y]){

					v[y]=1;

					q[ed++]=y;

				}

			}

		}

		++st;v[st]=0;

	}

}

inline int read(){

	int x=0; char c;

	do c=getchar(); while(c<'0'||c>'9');

	while(c>='0'&&c<='9')

		x=x*10+c-48,c=getchar();

	return x;

}

int main(){

	n=read();m=read();

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

		sx=read();sy=read();

		ins(sy,sx);

	}

	ST=read();ED=read();

	init();

	spfa();

	printf("%d",f[ST]);

}

巴特西

[NOIp2014] luogu P2296 寻找道路

题目描述

Solution

最新文章

热门文章