链接：poj 1422
题意：有n个点和m条有向边，现在要在点上放一些伞兵，伞兵可以沿着图走，
直到不能走为止，每条边有且仅有一个伞兵走过，问最少放多少个伞兵
思路：求的最小路径覆盖，用二分图来做
对于这样的一个有向图做最小路径覆盖，首先建图
然后每一条有向边对应左边的点指向右边的点
这样建好图之后求最大匹配数
最小路径覆盖=点数-最大匹配数
-
#include<stdio.h>
-
#include<string.h>
-
int n,edge[150][150],link[150],used[150];
-
int dfs(int pos)
-
{
-
int i;
-
for(i=1;i<=n;i++)
-
if(edge[pos][i]&&!used[i]){
-
used[i]=1;
-
if(link[i]==-1||dfs(link[i])){
-
link[i]=pos;
-
return 1;
-
}
-
}
-
return 0;
-
}
-
int main()
-
{
-
int T,i,m,a,b,s;
-
scanf("%d",&T);
-
while(T--){
-
scanf("%d%d",&n,&m);
-
memset(edge,0,sizeof(edge));
-
for(i=1;i<=m;i++){
-
scanf("%d%d",&a,&b);
-
edge[a][b]=1;
-
}
-
memset(link,-1,sizeof(link));
-
s=0;
-
for(i=1;i<=n;i++){
-
memset(used,0,sizeof(used));
-
s+=dfs(i);
-
}
-
printf("%d\n",n-s);
-
}
-
return 0;
-
}
poj 1422 Air Raid （最小路径覆盖）
原文：http://blog.csdn.net/acm_code/article/details/39852107
