Minimum path coverage of digraphs =V- Maximum matching of bipartite graph .

Consider a town where all the streets are one-way and each street leads from one intersection to another. It is also known that starting from an intersection and walking through town's streets you can never reach the same intersection i.e. the town's streets form no cycles.

With these assumptions your task is to write a program that finds the minimum number of paratroopers that can descend on the town and visit all the intersections of this town in such a way that more than one paratrooper visits no intersection. Each paratrooper lands at an intersection and can visit other intersections following the town streets. There are no restrictions about the starting intersection for each paratrooper.

InputYour program should read sets of data. The first line of the input file contains the number of the data sets. Each data set specifies the structure of a town and has the format:

no_of_intersections 
no_of_streets 
S1 E1 
S2 E2 
...... 
Sno_of_streets Eno_of_streets

The first line of each data set contains a positive integer no_of_intersections (greater than 0 and less or equal to 120), which is the number of intersections in the town. The second line contains a positive integer no_of_streets, which is the number of streets in the town. The next no_of_streets lines, one for each street in the town, are randomly ordered and represent the town's streets. The line corresponding to street k (k <= no_of_streets) consists of two positive integers, separated by one blank: Sk (1 <= Sk <= no_of_intersections) - the number of the intersection that is the start of the street, and Ek (1 <= Ek <= no_of_intersections) - the number of the intersection that is the end of the street. Intersections are represented by integers from 1 to no_of_intersections.

There are no blank lines between consecutive sets of data. Input data are correct. 
OutputThe result of the program is on standard output. For each input data set the program prints on a single line, starting from the beginning of the line, one integer: the minimum number of paratroopers required to visit all the intersections in the town. 
Sample Input

2
4
3
3 4
1 3
2 3
3
3
1 3
1 2
2 3

Sample Output

2
1
The question : To give you one DAG( Directed acyclic graph ), Minimum vertex coverage is required
Answer key : According to the formula DAG Minimum vertex cover =V- Maximum matching of bipartite graph
#include<map>
#include<set>
#include<cmath>
#include<queue>
#include<stack>
#include<vector>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define pi acos(-1)
#define ll long long
#define mod 1000000007 using namespace std; const int N=+,maxn=+,inf=0x3f3f3f3f; int n,color[N];
bool ok[N][N],used[N]; bool match(int x)
{
for(int i=;i<=n;i++)
{
if(ok[x][i]&&!used[i])
{
used[i]=;
if(color[i]==-||match(color[i]))
{
color[i]=x;
return ;
}
}
}
return ;
}
int solve()
{
int ans=;
memset(color,-,sizeof color);
for(int i=;i<=n;i++)
{
memset(used,,sizeof used);
ans+=match(i);
}
return ans;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie();
int t,m;
cin>>t;
while(t--){
memset(ok,,sizeof ok);
cin>>n>>m;
while(m--){
int a,b;
cin>>a>>b;
ok[a][b]=;
}
cout<<n-solve()<<endl;
}
return ;
}

hdu1151 Minimum vertex covering of digraph

  1. poj2594 Minimum vertex cover + Pass closures

    Passing closures starts with Floyd-Warshall In the algorithm , At that time, this algorithm was rarely used, so it was ignored by me .. Transitive closure means if i Can reach k, also k Can reach j, that i Can reach j Have you ever read a ...

  2. POJ2226 Muddy Fields Binary matching Minimum vertex cover Good question

    In a n*m On the grass ,. It's for grass ,* Representative water , Now we're going to use a width of 1, Boards of unlimited length cover the water , The boards can overlap , But all the grass can't be covered with planks . Ask at least the number of boards you need . The method of drawing this kind of problem : Take a matrix as a bipartite graph , With ...

  3. BZOJ 3140 disinfect ( Minimum vertex cover )

    Topic link :http://61.187.179.132/JudgeOnline/problem.php?id=3140 The question : I've been working in a biological laboratory recently T In great trouble .  Due to the recent upgrade of the laboratory , His division ...

  4. poj 3041 Asteroids ( Max match min vertex cover —— The Hungarian template question )

    http://poj.org/problem?id=3041 Asteroids Time Limit: 1000MS   Memory Limit: 65536K Total Submissions ...

  5. hdoj 1150 Machine Schedule【 hungarian algorithm + Minimum vertex cover 】

    Machine Schedule Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) ...

  6. HDU ACM 1054 Strategic Game Minimum vertex cover of bipartite graph ? Tree form DP

    analysis : Here we use the tree shape DP do . 1. Minimum vertex covering method : Minimum vertex cover == The biggest match ( Two way graph )/2. 2. Tree form DP: dp[i][0] Express i Root node , And the node doesn't put , Minimum number of points required . dp[i][1] Express ...

  7. hdu1054( Minimum vertex cover )

    Portal :Strategic Game The question : Cover all edges with as few vertices as possible . analysis : Minimum vertex covering problem , Minimum vertex cover = The maximum number of matches ( Two way graph )/2. #include <cstdio> #incl ...

  8. hdu 1150 Machine Schedule( Minimum vertex cover )

    pid=1150">Machine Schedule Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/327 ...

  9. hdu1054 Minimum vertex cover

    Minimum fixed-point coverage refers to such a situation : chart G The vertex covering of is a set of vertices V, bring G Every edge in the world touches V At least one vertex in . We call it a set V covers G The edge of . Minimum vertex covering is to cover all edges with the least number of vertices . The number of vertex covers is the minimum vertex cover ...

Random recommendation

  1. The Similarities and Differences Between C# and Java -- Part 1( translate )

    Original address Catalog Introduce (Introduction) Similarities (Similarities) Compilation unit (Compiled Units) Namespace (Namespaces) Top level members ( type )(Top Level ...

  2. Time --cd //lastyear

    Summer wood , Is there a car coming and going in heaven , Just like Nanjing in those days The noise of the streets , I know that even if it's prosperous , Still can't fill your bottomless loneliness ! It's just that I can't forget your face after seeing you in the crowd Is it true that you can get rid of thousands of worries when you are drunk How to say love ...

  3. WinAPI—— The composition of harmonic vibrations

    #include<Windows.h> #include<math.h> #define NUM 1000 #define PI 3.14159 LRESULT CALLBAC ...

  4. powerdesigener 12.5 Register machine

    Download link Download link password :awg9

  5. armeabi And armeabi-v7a

    original text http://blog.csdn.net/liminled/article/details/17030747 1.armeabi armeabi It means that so The library is used for Arm Common to CPU. 2.arme ...

  6. 1441: Min

    1441: Min Time Limit: 5 Sec  Memory Limit: 64 MBSubmit: 320  Solved: 213[Submit][Status][Discuss] De ...

  7. forget root password , Enter single user mode, change password

    Enter single user mode rhel61. In a few seconds of the system , Press the key , Go to the system boot menu in 2. After selecting the system Press “e” key choice kernel after Press “e” key Space after 1+ enter b: Start the system Enter single user mode rhel71. stay ...

  8. HDU 1495 Very cola ( number theory ,BFS)

    Very cola Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submi ...

  9. Python—— Use Goth API Get the specified City, specified category POI And implement XLSX File merge

    # The following is original , Reprint please indicate the source 1 import xlrd # read xlsx import xlsxwriter # Write xlsx import urllib.request # url request ,Pyth ...

  10. cocos2d-x The processing of playing video

    cocos2d-x It supports direct video playback , It's using Native The player on the Internet , The default level of video is in cocos Above the level of , If you want the video to have cocos Control for , Only the video can be UI The hierarchy is at the bottom , This method has been compared to ...