Treasure Exploration POJ - 2594 （最小路径覆盖+可重复点+Floyd传递闭包）

Treasure Exploration

Have you ever read any book about treasure exploration? Have you ever see any film about treasure exploration? Have you ever explored treasure? If you never have such experiences, you would never know what fun treasure exploring brings to you.
Recently, a company named EUC (Exploring the Unknown Company) plan to explore an unknown place on Mars, which is considered full of treasure. For fast development of technology and bad environment for human beings, EUC sends some robots to explore the treasure.
To make it easy, we use a graph, which is formed by N points (these N points are numbered from 1 to N), to represent the places to be explored. And some points are connected by one-way road, which means that, through the road, a robot can only move from one end to the other end, but cannot move back. For some unknown reasons, there is no circle in this graph. The robots can be sent to any point from Earth by rockets. After landing, the robot can visit some points through the roads, and it can choose some points, which are on its roads, to explore. You should notice that the roads of two different robots may contain some same point.
For financial reason, EUC wants to use minimal number of robots to explore all the points on Mars.
As an ICPCer, who has excellent programming skill, can your help EUC?

Input

The input will consist of several test cases. For each test case, two integers N (1 <= N <= 500) and M (0 <= M <= 5000) are given in the first line, indicating the number of points and the number of one-way roads in the graph respectively. Each of the following M lines contains two different integers A and B, indicating there is a one-way from A to B (0 < A, B <= N). The input is terminated by a single line with two zeros.

Output

For each test of the input, print a line containing the least robots needed.

Sample Input

Sample Output

1
1
2

这题跟1422原本以为一样求最短路径覆盖，后来知道，最短路径覆盖是每个点只能走一次，但是这个题目是可以走多次？我反复想就是不明白为什么？？

后来看了一个图明白了

Treasure Exploration POJ - 2594 （最小路径覆盖+可重复点+Floyd传递闭包）

比如直接求最短路径覆盖的话,上图情况如果求出1-2匹配，2-4匹配，那么3-2-5这条路径就已经被切断不存在了，因为2不能再走了

实际上2还是可以走的。按照上图，答案是5-最大匹配=5-2=3，实际上答案是2

因此这个题用floyd先求一次闭包，再次求解就行了。

转自：https://www.cnblogs.com/void/articles/2156423.html

题目链接：http://poj.org/problem?id=2594

在外星上有n个点需要机器人去探险，有m条单向路径。问至少需要几个机器人才能遍历完所有的点，一个点可以被多个机器人经过（这就是和单纯的最小路径覆盖的区别）。

因为图是一个有向图

例如 1—>3,

　　 2—>3;

　　 3—>4;

　　 3—>5;

左边是floyd之前的，右边是传递之后的，左边的最大匹配是2，右边是3；

其中为什么用传递闭包就能求最大匹配，自己只可意会不可言传；—_—;

转自：https://www.cnblogs.com/zhengguiping--9876/p/4726653.html

#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
const int N = 555;
int g[N][N];
int n, m;
/*int head[N], en;
struct Edge {
	int v, to;
} edge[111111];
void addedge (int u, int v) {
	edge[en].v = v;
	edge[en].to = head[u];
	head[u] = en++;
}*/
int link[N], in[N];
int dfs(int u) {
	/*for (int i = head[u]; ~i; i = edge[i].to) {
		int v = edge[i].v;
		if (!in[v]) {
			in[v] = 1;
			if (!link[v] || dfs(link[v])) {
				link[v] = u;
				return 1;
			}
		}
	}*/
	for (int v = 1; v <= n; ++v) {
		if (g[u][v] && !in[v]) {
			in[v] = 1;
			if (!link[v] || dfs(link[v])) {
				link[v] = u;
				return 1;
			}
		}
	}
	return 0;
} 
void floyd() {
	
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= n; ++j) {
			for (int k = 1; k <= n; ++k) {
				if (g[i][k] && g[k][j]) g[i][j] = 1;
			}
		}
	}
	
}

int main() {
	
	
	while (~scanf ("%d %d", &n, &m) && (n + m)) {
		//memset(head, -1, sizeof(head));
		//en = 0;
		memset(g, 0, sizeof(g));
		int u, v;
		for (int i = 1; i <= m; ++i) {
			scanf ("%d %d", &u, &v);
			g[u][v] = 1;
			//addedge(u, v);
		}
		floyd(); // 
		memset (link, 0, sizeof(link));
		int ans = 0; 
		for (int i = 1; i <= n; ++i) {
			 memset(in, 0, sizeof(in));
			 if (dfs(i)) ++ans;
		}
		printf ("%d\n", n - ans);
	}
	
	return 0;
}

Treasure Exploration POJ - 2594 （最小路径覆盖+可重复点+Floyd传递闭包）

Treasure Exploration

相关推荐