轉(zhuǎn)：
http://caojia321.blogchina.com/2415567.html

最小路徑覆蓋
[ 2006-9-11 10:57:00 | By: Irvin ]
?

最小路徑覆蓋：
該問題就是求一個(gè)邊的集合的個(gè)數(shù)，集合滿足下述條件：
1 集合之中不能有相交邊，卻是一個(gè)通路。
2 所有的集合中的邊要覆蓋所有的頂點(diǎn)。
3 集合個(gè)個(gè)數(shù)最少
注：求最小路徑覆蓋的前提是該圖是有向無環(huán)圖。所以answer＝頂點(diǎn)數(shù)－最小覆蓋的邊數(shù)

該問題可以轉(zhuǎn)化成二分匹配來做：
怎樣構(gòu)造二分圖：
1 把一個(gè)頂點(diǎn)i劃分成兩個(gè)頂點(diǎn)Xi和Yi
2 如果頂點(diǎn)i到j(luò)可達(dá)，則Xi指向Yi

分析：
由于是有向無環(huán)圖，所以每次匹配都不可能形成環(huán)，也就是不可能有兩個(gè)不同的點(diǎn)
指向同一個(gè)點(diǎn)，這樣每加進(jìn)一條邊，覆蓋的點(diǎn)數(shù)就會(huì)多一個(gè)。最大匹配數(shù)就是最小覆蓋的邊數(shù)。

題目：http://acm.pku.edu.cn/JudgeOnline/problem?id=1422
#include<stdio.h>
#include<memory.h>
const?int?MAX=121;
int?c[MAX][MAX];
int?link[MAX];
bool?s[MAX];
int?n;
bool?find(int?x)
{
????int?i;
????for(i=1;i<=n;i++){
????????if((!s[i])&&c[x][i]!=0){
????????????s[i]=true;
????????????if(link[i]==0||find(link[i])){
????????????????link[i]=x;
????????????????return?true;
????????????}
????????}
????}
????return?false;
}
int?main()
{
????int?i;
????int?t,m;
????int?a,b;
????int?ans;
????scanf("%d",&t);
????while(t--){
????????scanf("%d%d",&n,&m);
????????memset(c,0,sizeof(c));
????????memset(link,0,sizeof(link));
????????for(i=0;i<m;i++){
????????????scanf("%d%d",&a,&b);
????????????c[a][b]=1;
????????}
????????ans=0;
????????for(i=1;i<=n;i++){
????????????memset(s,false,sizeof(s));
????????????if(find(i)){
????????????????ans++;
????????????}
????????}
????????printf("%d\n",n-ans);
????}
????return?0;
}