当前位置:网站首页>379. hide and seek
379. hide and seek
2022-06-24 23:21:00 【Searching for people far away】
Vani and cl2 Playing hide and seek in a forest .
There are... In this forest N Houses ,M A directed road , It forms a directed acyclic graph .
The trees in the woods are very dense , Enough to block the line of sight , But looking down the road , But it has a wide view .
If from the house A Go down the road and you can reach B, So in A and B People in the can see each other .
Now? cl2 Here you are N Choose... From this house K As a hiding place , meanwhile Vani Also pick cl2 A house as a hiding place to go in and look for , To avoid being Vani See ,cl2 Ask for this K There is no path between any two hiding places .
In order to make Vani It's harder to find yourself ,cl2 Want to know the maximum number of hiding places you can choose .
Input format
The first line of input data is two integers N and M.
Next M That's ok , Two integers per line x,y, Represents a path from x To y The directed path .
Output format
Output an integer , Indicates the maximum number of hiding places that can be selected .
Data range
N≤200,M≤30000
sample input :
7 5
1 2
3 2
2 4
4 5
4 6
sample output :
3
Ideas :
/* Minimum path coverage : For a directed acyclic graph (DAG), Use the least number of disjoint paths , Cover all points .( Among them, disjoint means that the points are not repeated ) Conclusion : Minimum path point coverage ( Minimum path coverage ) = Total points - The biggest match prove : 1. Drawing Finding the minimum path cover uses the disassembly point , A point is divided into two points , Points and entry points are shown respectively , So from the point i->j Just use one side of the , From the point on the left i Connect to the right entry point j’ Express , The resulting graph is a bipartite graph , Because all the edges are between the left and right , There is no point inside . 2. conversion At this point, each path in the original graph is converted to the new graph , Because the paths in the original graph do not intersect with each other , So each point has at most one out degree and one in degree , This means that in the new picture , Each point on the left can only be connected to one edge on the right at most , The point on the right will only have one edge connected at most , Each point can only belong to one edge at most . ① A path in the original figure <=> A set of matches in the new graph ( Each point in the new graph can only belong to one edge at most ) ② The end point of each path in the original figure ( No way out )<=> The unmatched points on the left of the new graph 3. deduction Find the number of disjoint paths in the original graph <=> Find the minimum number of end points of the path <=> Find the least left non matching points <=> Maximum matching expand : Minimum path repeat point coverage : On the basis of the minimum path covering problem , Remove disjoint . Conclusion : Original drawing G, Find the graph after transitive closure G’, be G Minimum path repeat point coverage =G’ Minimum path coverage of In this question , Note that the minimum path repeat point coverage is cnt, The answer to this question is cnt prove : ①k<=cnt this cnt This path covers all the points , So what you ask for k A point must be from here cnt Click in the path , And select at most one point on each path , therefore k<=cnt ②k>=cnt structure : take cnt The ends of all paths are put into a set E in , remember next(E) The return is from E A collection of all points that can be reached from each point in the Classification of discussion : i)E ∩ next(E) = Ø , here E Points within cannot reach each other , explain E All points in the are one k=cnt The plan ii)E ∩ next(E) ≠ Ø , about E Any point in p, Let this point go in the opposite direction , Until this point to a not next(E-p) In the point , It can be proved that when this point reaches the starting point, it must not be next(E-p) in . Reduction to absurdity : If this point comes to the starting point , Still in next(E-p) in , explain p The starting point of the path can be reached by other paths , Then this path has no meaning of existence and can be omitted , Does not satisfy the minimum path repeat point coverage . So you can also select a point in each path , Make these points unreachable in pairs , namely k=cnt */
Code :
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 210, M = 30010;
int n, m;
bool d[N][N], st[N];
int match[N];
bool find(int x)
{
for (int i = 1; i <= n; i ++ )
if (d[x][i] && !st[i])
{
st[i] = true;
int t = match[i];
if (t == 0 || find(t))
{
match[i] = x;
return true;
}
}
return false;
}
int main()
{
scanf("%d%d", &n, &m);
while (m -- )
{
int a, b;
scanf("%d%d", &a, &b);
d[a][b] = true;
}
// Pass closures
for (int k = 1; k <= n; k ++ )
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= n; j ++ )
d[i][j] |= d[i][k] & d[k][j];
int res = 0;
for (int i = 1; i <= n; i ++ )
{
memset(st, 0, sizeof st);
if (find(i)) res ++ ;
}
printf("%d\n", n - res);
return 0;
}
边栏推荐
- F29oc analysis
- #22Map介绍与API
- Theoretical analysis of countermeasure training: adaptive step size fast countermeasure training
- 【js】-【树】-学习笔记
- Notes for laravel model
- laravel model 注意事项
- 03_SpingBoot 核心配置文件
- UNION ALL UNION FULL JOIN
- Case analysis: using "measurement" to improve enterprise R & D efficiency | ones talk
- 推送Markdown格式信息到钉钉机器人
猜你喜欢

Blogs personal blog test point (manual test)

记录一下MySql update会锁定哪些范围的数据

Main cause of EMI - mold current

A big factory interview must ask: how to solve the problem of TCP reliable transmission? 8 pictures for you to learn in detail

03_ Spingboot core profile

03_SpingBoot 核心配置文件

Epics record reference 2 -- epics process database concept

Canvas to add watermark to pictures
![[JS] - [array, stack, queue, linked list basics] - Notes](/img/c6/a1bd3b8ef6476d7d549abcb442949a.png)
[JS] - [array, stack, queue, linked list basics] - Notes

vulnhub DC: 2
随机推荐
jar中没有主清单属性
22map introduction and API
2022 safety officer-b certificate examination question bank and answers
監聽 Markdown 文件並熱更新 Next.js 頁面
376. 机器任务
Force deduction solution summary 515- find the maximum value in each tree row
常用正则表达式
斐波那契
数字IC设计经验整理(二)
[JS] - [linked list - application] - learning notes
02_ Springboot starter case
Main cause of EMI - mold current
378. Knight placement
2022 safety officer-a certificate examination questions and answers
Construction equipment [5]
#22Map介绍与API
Accounting standards for business enterprises application [5]
Construction equipment [6]
Blogs personal blog project details (servlet implementation)
Detailed explanation of online group chat and dating platform project (servlet implementation)