HDU|HDU -1151 二分匹配与DAG图（最小覆盖路径） HDU-1151二分匹配与DAG图（最小覆

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

题目描述：城镇里的街道从一个交叉口连接到另一个交叉口，街道都是单向的，并且从一个交叉口沿着街道出发不会回到相同的交叉口。伞兵降临在城镇的一个交叉口并可以沿着街道走向另一个没有被其他伞兵走过的交叉口，问城镇中的所有交叉口都被伞兵走过的情况下至少需要多少名伞兵。
算法分析：从题目中介绍城镇和街道的信息中可以知道是一个有向无环图，最少伞兵数量=DAG的最少路径覆盖（关于最少路径覆盖）

最小路径覆盖】
首先给出公式:DAG的最小路径覆盖数=DAG图中的节点数-相应二分图中的最大匹配数.
【HDU|HDU -1151 二分匹配与DAG图（最小覆盖路径）】一个PXP的有向图中，路径覆盖就是在图中找一些路径，使之覆盖了图中的所有顶点，且任何一个顶点有且只有一条路径与之关联；（如果把这些路径中的每条路径从它的起始点走到它的终点，那么恰好可以经过图中的每个顶点一次且仅一次）；如果不考虑图中存在回路，那么每条路径就是一个弱连通子集。
由上面可以得出： 1.一个单独的顶点是一条路径； 2．如果存在一路径p1,p2,......pk，其中p1 为起点，pk为终点，那么在覆盖图中，顶点p1,p2,......pk不再与其它的顶点之间存在有向边．对于一个路径覆盖，有如下性质： 1、每个顶点属于且只属于一个路径。 2、路径上除终点外，从每个顶点出发只有一条边指向路径上的另一顶点。那么对应一个DAG,如何构造相应的二分图?对于DAG中的一个顶点p,二分图中有两个顶点p和p',对应DAG中的一条有向边p->q,二分图中有p-q'的一条无向边.二分图中p属于S集合,p'属于T集合.

文章图片
上图中,对应左边的DAG建立构造右边的二分图,可以找到二分图的一个最大匹配M:1-3',3-4',那么M中的这两条匹配边怎样对应DAG中的路径的边? 使二分图中一条边对应DAG中的一条有向边,1-3'对应DAG图中的有向边1->3,这样DAG中1就会有一个后继顶点(3会是1的唯一后继,因为二分图中一个顶点至多关联一条边!),所以1不会成为DAG中一条路径中的结尾顶点,同样,3-4'对应DAG中3->4,3也不会成为结尾顶点,那么原图中总共4个顶点,减去2个有后继的顶点,就剩下没有后继的顶点,即DAG路径的结尾顶点,而每个结尾顶点正好对应DAG中的一条路径,二分图中寻找最大匹配M,就是找到了对应DAG中的非路径结尾顶点的最大数目,那么DAG中顶点数-|M|就是DAG中结尾顶点的最小数目,即DAG的最小路径覆盖数.即上图中找到的最小路径覆盖集合为2， 1->3->4。参考博客： http://www.cnblogs.com/icode-girl/p/5418461.html http://www.cnblogs.com/justPassBy/p/5369930.html http://www.bubuko.com/infodetail-640189.html #include#include#include#include#include#include#define inf 0x7fffffffusing namespace std; const int maxn=240+10; int n,m; int g[maxn][maxn],linker[maxn],vis[maxn]; int dfs(int u){for (int v=1 ; v<=n ; v++) if (g[u][v]){if (!vis[v]){vis[v]=1; if (linker[v]==-1 || dfs(linker[v])){linker[v]=u; return 1; }}}return 0; }int hungary(){int ans=0; for (int i=n+1 ; i<=2*n ; i++){memset(vis,0,sizeof(vis)); if (dfs(i)) ans++; }return ans; }int main(){int t; scanf("%d",&t); while (t--){scanf("%d%d",&n,&m); memset(g,0,sizeof(g)); memset(linker,-1,sizeof(linker)); int x,y; for (int i=0 ; i