poj 1422 Air Raid（最小路径覆盖 + 二分图最大匹配）

本文主要是介绍poj 1422 Air Raid（最小路径覆盖 + 二分图最大匹配），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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;
}