大飞同学问我这一题, 图论的东西我是一点都没看过, 直接看了discuss
做这题用了得有十个小时.. 我可是连二分图都不知道是什么..
然后什么是二分图匹配呢

而

最小覆盖数 == 节点数 – 最大匹配数

为什么呢, 数学归纳一下, 匹配数为0时显然 最小覆盖数 == 节点数, 然后有一个二分图匹配就能把两个覆盖路径合二为一, 很简单. 具体的在ufo008ahw这里有所说明
扩展阅读： Matrix67牛有一篇文章介绍了二分图最大匹配的König定理及其证明

求二分图最大匹配用匈牙利算法或者最大流(这个我还没看- -).
有向图转化成二分图很简单, 把每个节点变成两个节点(在二分图两边)一个负责入一个负责出即可

至此我们已经可以解决有向图的最小路径覆盖问题. 允许路径重叠的情况怎么办呢, 明显是要转化成不允许路径重叠的情况来依葫芦画瓢, 想要在求二分图最大匹配的过程中考虑允许重叠的情况我想过.. 没想出来, 难度吹牛逼一样.

怎样转化: 用Floyd求一下传递闭包即可, 这个我想了好久才明白, 我来说明一下
比如有向图G: 1->2->3 4->2->5
解释是: 对于任何的有重复节点的路径, 比如这里的2, 求了传递闭包以后的图就会包含1->3和4->5这两个路径, 实现”跳过去”的走法

Floyd没什么好说的, 关于匈牙利算法(初次接触)的一些细节:

1. 下面这个代码的我是看的这里, 这个数据结构和递归太牛了..做完我整个人都犀利了. 它是只记y指向x不记x指向y, 每次对x搜索可用的y, 而不是记录它们, 整个操作都简单了好多. 原文的注释写的很好
2. 代码中的visited[] 这个验证我列举了各种情况, 是正确的, 有点难度
3. 算法的原理我很清楚了. 但是代码里x和y双重循环, 为什么x和y各循环一遍就ok了我还是没有理解太透彻, 这也是匈牙利算法的精髓吧

代码点下面:

#include <stdio.h>
#include <string.h>

void floydMap(bool a[][501],bool A[][501],int N) {
    for(int i=1;i<=N;i++)
        for(int j=1;j<=N;j++)
            a[i][j]=A[i][j];

    for(int k=1;k<=N;k++)
        for(int i=1;i<=N;i++)
            for(int j=1;j<=N;j++) {
                if(i==j || a[i][j])
                    continue;
                if(a[i][k] && a[k][j])
                    a[i][j]=true;
            }
    return;
}

bool orz(bool a[][501],int N,int x,bool visited[501],int yRefer[501]) {
    for(int y=1;y<=N;y++) {
        if(visited[y] || !a[x][y])
            continue;

        visited[y]=true;
        if(yRefer[y]==-1 || orz(a,N,yRefer[y],visited,yRefer) ) {
            yRefer[y]=x;
            return true;
        }
    }
    return false;
}

int maxMatch(bool a[][501],int N) {
    int yRefer[501];
    memset(yRefer,0xff,sizeof(yRefer));

    bool visited[501];
    int result=0;
    for(int i=1;i<=N;i++) {
        memset(visited,0x00,sizeof(visited));
        if(orz(a,N,i,visited,yRefer))
            result++;
    }

    return result;
}

int main() {
    while(1) {
        int N,M;
        scanf("%d%d",&N,&M);
        if(!N)
            break;

        bool MAP[501][501];
        memset(MAP,0x00,sizeof(MAP));
        for(int i=0;i<M;i++) {
            int from,to;
            scanf("%d%d",&from,&to);
            MAP[from][to]=true;
        }

        bool fm[501][501];
        floydMap(fm,MAP,N);

        int m;
        m=maxMatch(fm,N);

        printf("%d\n",N-m);
    }
    return 0;
}