题目大意：
在一个城镇，有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]=true;
}
}
bool can(int t)
{
for(int i=1;i<=no_of_intersections;i++)
{
if(!useif ;; map[t])
{
useif=true;
if(link==-1 || can(link))
{
link=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
