转：
http://caojia321.blogchina.com/2415567.html

最小路径覆盖
[ 2006-9-11 10:57:00 | By: Irvin ]
 

最小路径覆盖：
该问题就是求一个边的集合的个数，集合满足下述条件：
1 集合之中不能有相交边，却是一个通路。
2 所有的集合中的边要覆盖所有的顶点。
3 集合个个数最少
注：求最小路径覆盖的前提是该图是有向无环图。所以answer＝顶点数－最小覆盖的边数

该问题可以转化成二分匹配来做：
怎样构造二分图：
1 把一个顶点i划分成两个顶点Xi和Yi
2 如果顶点i到j可达，则Xi指向Yi

分析：
由于是有向无环图，所以每次匹配都不可能形成环，也就是不可能有两个不同的点
指向同一个点，这样每加进一条边，覆盖的点数就会多一个。最大匹配数就是最小覆盖的边数。

题目：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;
}