本文写于 2019年03月27日,距今已超过 1 年,距 2020年03月27日 的最后一次修改也已超过 3 个月,部分内容可能已经过时,您可以按需阅读。如果图片无法显示或者下载链接失效,请给我反馈,谢谢!


0 0 投票数
评分

我感觉这道题有点难度的,错了很多次。

但是如果把事情说清楚,其实一点难度也没有,就是连续 2 次 BFS。甚至在处理哪些点是合法的这个过程中,都比《逃跑》那题要简单很多,因为没有时间的维度,也不存在间隔 t 循环射击,所以只需要考虑有出边到那些不可达终点的点都是不合法的就可以了。

关键是,不容易想到。

整体的思路是,反向建边(在 insert 边的时候把起点和终点调换),然后从终点开始,BFS 一次,找到哪些点是不能到达终点的,标记下来,然后根据这些标记,判断哪些点是合法的,最后从终点开始反向 BFS,找到的最短路就是答案。

由于是反向建图的,所以所有的操作都是反向 BFS,如果正向判断,就会因为多次遍历所有的点找邻居而超时。

找哪些点是终点可达的时候,扫描一次就可以了,没有必要每个点都扫描。

代码其实很短,就是裸的广搜,没有很复杂的处理过程,下面代码比较长是因为中间加了很多注释,而且有些超时的写法没有删掉。

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {

	private static boolean[] terminalReachablePoints;
	private static boolean[] validPoints;
	private static boolean[] visited;
	private static HashMap<Integer, ArrayList<Integer>> g;
	private static int n;
	private static int s;
	private static int t;
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		n  = in.nextInt();
		int m = in.nextInt();
		terminalReachablePoints = new boolean[n + 1];
		
		g = new HashMap<>();
		for (int i = 1; i <= n; i++)
			g.put(i, new ArrayList<>());
		for (int i = 0; i < m; i++) {
			int x = in.nextInt();
			int y = in.nextInt();
			g.get(y).add(x);
		}
		s = in.nextInt();
		t = in.nextInt();
		in.close();
		
		//只需要调用一次,计算出所有点的可达性就可以了,没必要每个点都调用一次
		/*
		 * 这会超时 
	private static boolean canPointBeTerminalReachable(int VirtualTerminal) {
		Queue<Integer> q = new LinkedList<Integer>();
		q.add(t);
		visited[t] = true;
		while (!q.isEmpty()) {
			int current = q.poll();
			if (current == VirtualTerminal) {
				return true;
			} else {
				for (int neighbour : g.get(current)) {
					if (!visited[neighbour]) {
						visited[neighbour] = true;
						q.add(neighbour);
					}
				}
			}
		}
		return false;
	}
		 */
		visited = new boolean[n + 1];
		findTerminalReachablePoints(); // 第 1 次 BFS
		
//		for (int i = 1; i <= n; i++)
//			System.out.println(i + ":" + terminalReachablePoints[i]);
		
		/*
		 * 要弄清楚 "x 可以到达终点 t" 和 "x 是合法的点" 的区别
		 * 
		 * 以下数据就会得到 -1,而事实是 1:
		 * 5 5 4 5 4 3 3 5 3 2 2 1 4 5
		 * 
		 * 下面的代码会把这两点混在一起,只用了一个terminalReachable[i]来表示
		 */
//		for (int i = 1; i <= n; i++) 
//			if (!terminalReachablePoints[i]) 
//				for (int x : g.get(i)) 
//					terminalReachablePoints[x] = false;
		
		// 计算合法的点
		validPoints = new boolean[n + 1];
		for (int i = 1; i <= n; i++)
			validPoints[i] = terminalReachablePoints[i];
		// 默认值直接用是不是可达,不能默认 true/false,否则代码下附的数据,10 号合法性会错
		for (int i = 1; i <= n; i++)
			if (!terminalReachablePoints[i])
				for (int x : g.get(i))
					validPoints[x] = false;
		
//		for (int i = 1; i <= n; i++)
//			System.out.println(i + ":" + validPoints[i]);
		
		visited = new boolean[n + 1];
		int ans = bfs(); // 第 2 次 BFS
		
		System.out.println(ans);
	}

	private static void findTerminalReachablePoints() {
		Queue<Integer> q = new LinkedList<Integer>();
		q.add(t);
		visited[t] = true;
		while (!q.isEmpty()) {
			int current = q.poll();
			terminalReachablePoints[current] = true;
			for (int neighbour : g.get(current)) {
				if (!visited[neighbour]) {
					visited[neighbour] = true;
					q.add(neighbour);
				}
			}
		}
	}

	private static int bfs() {
		Queue<Integer> q = new LinkedList<Integer>();
		Queue<Integer> steps = new LinkedList<Integer>();
		q.add(t); // 也是反着来,否则会超时
		steps.add(0);
		visited[s] = true;
		while (!q.isEmpty()) {
			int current = q.poll();
			int step = steps.poll();
			if (current == s) {
				return step;
			} else {
				for (int neighbour : g.get(current)) {
					if (!validPoints[neighbour]) // 合法的点,和能到终点的点不一样
						continue;
					visited[neighbour] = true;
					q.add(neighbour);
					steps.add(step + 1);
				}
			}
		}
		return -1;
	}
	
	// 如果 BFS 从 s 开始找到 t,就不得不遍历所有点,找到给定点的邻居,会超时
	/*
		private static HashSet<Integer> getNeighbours(int current) {
		HashSet<Integer> neighbours = new HashSet<>();
		for (int x = 1; x <= n; x++) 
			if (terminalReachable[x] && !visited[x]) 
//				for (int y : g.keySet()) 
					if (g.get(x).contains(current)) 
						neighbours.add(x);
		return neighbours;
	}
	 */
	

/*
10 15
9 6
6 4
1 7
7 8
8 2
2 3
3 5
9 10
6 10
4 10
4 6
6 8
1 6
7 1
6 2
1 5
这组数据答案是 5
 */
}
0 0 投票数
评分
发表留言
订阅评论
提醒
guest

在点击发表评论按钮时,网络请求的数据包含浏览器版本、操作系统版本和 IP 地址;您的网络服务提供商、雇主或学校、政府机构可能会看到您的访问活动;根据浏览器默认行为、操作系统设置和安全防护软件的设置不同,您的浏览器可能会也可能不会在本地 Cookies 缓存您输入的用户名、邮箱以便下次评论使用。

请对自己的言行负责。

您想以什么身份发表评论
邮箱将在您的评论被回复时给您通知
(可选)如果您也有个人网站,不妨分享一下
我对这篇文章的评分
这篇文章给您带来多大帮助
0 评论
内联反馈
查看所有评论