题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1151
/* 题意大致为: 有一个城镇,它的所有街道都是单行的,并且每条街道都是和两个路口相连。同时已知街道不会形成回路。 你的任务是编写程序求最小数量的伞兵,这些伞兵可以访问(visit)所有的路口。对于伞兵的起始降落点不做限制 DAG图最小路径覆盖题,匈牙利法先求最大匹配max,最小路径覆盖=n(顶点数) - max; */ #include <iostream> using namespace std; const int MAX = 121; int linked[MAX][MAX]; int crossPath[MAX]; bool visited[MAX]; int n; bool search(int u) { for (int i = 1; i <= n; i ++) { if (linked[i][u] && !visited[i]) { visited[i] = true; if (crossPath[i] == -1 || search(crossPath[i])) { crossPath[i] = u; return true; } } } return false; } int maxMatch() { int count = 0; memset(crossPath, -1, sizeof(crossPath)); for (int i = 1; i <= n; i++) { memset(visited, false , sizeof(visited)); if (search(i)) count++; } return count; } int main() { int t, k, a, b; cin >> t; while (t--) { memset(linked, false, sizeof(linked)); cin >> n >> k; while (k--) { cin >> a >> b; linked[a][b] = true; } cout << (n - maxMatch()) << endl; } return 0; }