锐客网

  1. 首页 > it技术 > >

[HDU 1151] Air Raid 最小路径覆盖

http://acm.hdu.edu.cn/showproblem.php?pid=1151
题意：在一个城镇，有m个路口，和n条路，这些路都是单向的，而且路不会形成环，现在要弄一些伞兵去巡查这个城镇，伞兵只能沿着路的方向走，问最少需要多少伞兵才能把所有的路口搜一遍。
【[HDU 1151] Air Raid 最小路径覆盖】思路：其实就是就求最小路径覆盖，对于有向无环图，最小路径覆盖 = 顶点数 - 最大匹配。

#include #include #include #include using namespace std; const int maxn = 125; int n, m; int pre[maxn]; bool vis[maxn]; vector mapn[maxn]; bool hungary(int rt) { int len = mapn[rt].size(); for(int i = 0; i < len; i++){ int now = mapn[rt][i]; if(!vis[now]){ vis[now] = true; if(pre[now] == -1 || hungary(pre[now])){ pre[now] = rt; return true; } } } return false; }int main() { int Test; scanf("%d", &Test); while(Test--){ int x, y; scanf("%d%d", &n, &m); for(int i = 0; i <= n; i++){ mapn[i].clear(); } for(int i = 0; i < m; i++){ scanf("%d%d", &x, &y); mapn[x].push_back(y); } int sum = 0; memset(pre, -1, sizeof(pre)); for(int i = 1; i <= n; i++){ memset(vis, false, sizeof(vis)); sum += hungary(i); } printf("%d\n", n-sum); } return 0; }

    推荐阅读


    上一篇：ERROR in ./src/css/main.css Module build failed: Unknown word (5:1)

    下一篇：求割点和桥的DFS