http://poj.org/problem?id=1422
题意：在一个有向无环图中，从一些顶点出发，能遍历到图上所有点，要求初始选择的顶点数最少且顶点不重复遍历。
思路：
如果从某个顶点开始遍历的过程看成是路径的选择，那么问题就转化为在有向无环图中找最少的不想交的简单路径，这些路径覆盖图中的所有顶点。可见是关于最小路径覆盖的问题。
在有向无环图中，最小路径覆盖数 = 节点数 — 其对应二分图的最大匹配数。
最小路径覆盖它要求原图必须是有向无环图。然后根据原图构造二分图，方法为：将原图中的每个顶点vi一分为二，vi* 和vi**,相应的，如果原图中存在一条从vi到vj的有向边，那么就在顶点 vi* 和 vj** 之间连一条无向边，这就构造出一个路径覆盖问题所对应的二分图，在该二分图的基础上求其最大匹配数。
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int maxn = 130;
int n,m;
bool map[maxn][maxn];
int match[maxn];
int chk[maxn];
bool dfs(int p)
{
for(int i = 1; i <= n; i++)
{
if(map[p][i] && !chk[i])
{
chk[i] = 1;
if(match[i] == -1 || dfs(match[i]))
{
match[i] = p;
return true;
}
}
}
return false;
}
int main()
{
int test;
int x,y;
scanf("%d",&test);
while(test--)
{
memset(map,false,sizeof(map));
scanf("%d %d",&n,&m);
for(int i = 0; i < m; i++)
{
scanf("%d %d",&x,&y);
map[x][y] = true; //构造二分图
}
memset(match,-1,sizeof(match));
int res = 0;
for(int i = 1; i <= n; i++)
{
memset(chk,0,sizeof(chk));
if(dfs(i)) res += 1;
}
printf("%d\n",n-res);
}
return 0;
}