?

题目大意：
一个有向图中， 有若干条连接的路线， 问最少放多少个机器人，可以将整个图上的点都走过。 最小路径覆盖问题。

分析：
这时最小路径覆盖问题， 最小路径覆盖 = |V| - 最大匹配数。 （有关最小路径覆盖，最大匹配问题，相关概念不懂得点这里） 当然做这道题还有一个坑！！ 如果有向图的边有相交的情况，那么就不能简单的对原图求二分匹配了 详细讲解看这

#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         using namespace std; int n, m, sum, ans[505], v[505], map[505][505]; void floyd() // 求图的闭包 { for(int k = 1; k <= n; k++) { for(int i = 1; i <= n; i++) { if(map[i][k] == 1) { for(int j = 1; j <= n; j++) { if(map[k][j] == 1) map[i][j] = 1; } } } } } int dfs(int x) // 找增广路径 { for(int i = 1; i <= n; i++) { if(map[x][i] == 1 && v[i] == 0) { v[i] = 1; if(ans[i] == 0 || (ans[i] != 0 && dfs(ans[i]) == 1)) { ans[i] = x; return 1; } } } return 0; } int main() { while(scanf(%d%d, &n, &m) != EOF && (n || m)) { memset(ans, 0, sizeof(ans)); memset(map, 0, sizeof(map)); for(int i = 1; i <= m; i++) { int x, y; scanf(%d%d, &x, &y); map[x][y] = 1; } floyd(); sum = 0; for(int i = 1; i <= n; i++) // 求最大匹配 { memset(v, 0, sizeof(v)); int t = dfs(i); if(t == 1) sum++; } printf(%d , n - sum); } return 0; }