首页 > 代码库 > POJ2594 Treasure Exploration[DAG的最小可相交路径覆盖]
POJ2594 Treasure Exploration[DAG的最小可相交路径覆盖]
Treasure Exploration
Time Limit: 6000MS | Memory Limit: 65536K | |
Total Submissions: 8301 | Accepted: 3402 |
Description
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?
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
1 02 11 22 00 0
Sample Output
112
Source
POJ Monthly--2005.08.28,Li Haoyuan
Problem : Treasure Exploration
Description : 机器人探索宝藏,有N个点,M条边。问你要几个机器人才能遍历所有的点。
Solution : 二分图的最小路径覆盖。这个题看来好像就是裸的最小路径覆盖,但是题中说了一个点可以遍历多次,这和最小路径覆盖中路径之间不能有交点是矛盾的。那么怎么办呢,我们跑一遍floyd算法,来求出它的传递闭包,这样就可以构造一个新的图了。为什么可以这样呢,因为这样可以新增加边,使得原来路径不能共用同一个点的问题解决了,画个图就明白了。
如果不跑Floyd,那么最小路径覆盖数就是3,{[1->2->3],[4],[5]};跑一下传递闭包,就新增了两条边,如图中虚线所示,这时候4和5这两个点就可以直接连接了,因为[1->2->3]变成了[1->3]给[4->5]让开了一条路。因此以后如果不要求一个点只能走一次,那么就要跑floyd算法。
#include<cstdio>#include<cstring>using namespace std;const int N=510;int n,m,match[N],f[N][N];bool vis[N];void init(){ for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ f[i][j]=0; } } for(int i=1;i<=n;i++) match[i]=0;}bool hunguary(int x){ for(int i=1;i<=n;i++){ if(!vis[i]&&f[x][i]){ vis[i]=1; if(!match[i]||hunguary(match[i])){ match[i]=x; return 1; } } } return 0;}void floyed(){ for(int k=1;k<=n;k++){ for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ if(f[i][k]&&f[k][j]){ f[i][j]=1; } } } }}void solve(){ int ans=0; for(int i=1;i<=n;i++){ memset(vis,0,sizeof vis); if(hunguary(i)) ans++; } printf("%d\n",n-ans);}int main(){ while(scanf("%d%d",&n,&m)==2,n+m){ init(); for(int i=1,x,y;i<=m;i++) scanf("%d%d",&x,&y),f[x][y]=1; floyed(); solve(); } return 0;}
POJ2594 Treasure Exploration[DAG的最小可相交路径覆盖]
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。