HDU 1151 Air Aaid最小路径覆盖

题目大意：
在一个城镇，有m个路口，和n条路，这些路都是单向的，而且路不会形成环，现在要弄一些伞兵去巡查这个城镇，
伞兵只能沿着路的方向走，问最少需要多少伞兵才能把所有的路口搜一遍。这个题目就转换成求解有向无环图的最
小路径覆盖问题了。
一个结论：有向无环图的最小路径覆盖=该图的顶点数-该图的最大匹配。
 
AC代码：
[cpp]
#include<iostream> 
using namespace std; 
 
const int MAX=121; 
int no_of_intersections,no_of_streets,t; 
int link[MAX];    //记录当前与street终点相连的起点点 
bool map[MAX][MAX];  //存储二分图，起点到终点有路径，则map[x][y]=true;反之，为false 
bool useif[MAX];   //记录路口点是否使用了） 
 
void getMap()  //存图 
{ 
    memset(map,false,sizeof(map)); 
 
    int a,b; 
    for(int i=1;i<=no_of_streets;i++) 
    { 
        cin>>a>>b; 
        map[a][b]=true; 
    } 
} 
 
bool can(int t) 
{ 
    for(int i=1;i<=no_of_intersections;i++) 
    { 
        if(!useif[i] && map[t][i]) 
        { 
            useif[i]=true; 
            if(link[i]==-1 || can(link[i])) 
            { 
                link[i]=t; 
                return true; 
            } 
        } 
    } 
 
    return false; 
} 
 
int maxMatch() 
{ 
    int num=0; 
 
    memset(link,int(-1),sizeof(link));  //未连的计为-1 
    for(int i=1;i<=no_of_intersections;i++)   //从street起点开始依次搜索增广路经 
    { 
        memset(useif,false,sizeof(useif)); 
        if(can(i)) num++; 
    } 
 
    return num; 
} 
 
int main() 
{ 
    cin>>t; 
    while(t--) 
    { 
        cin>>no_of_intersections>>no_of_streets; 
 
        getMap(); 
 
        cout<<no_of_intersections-maxMatch()<<endl; 
    } 
 
    return 0; 
} 

摘自 ON THE WAY