http://acm.hdu.edu.cn/showproblem.php?pid=1151最小路径覆盖也就是求出最少的路径将所有点都包含进去。
有向图的最小路径覆盖=V-二分图最大匹配。
这道题求最少的士兵数能够访问到所有的节点，有向图的路径跟无向图的不一样：
如图，需要两条路径1-3-4、2-3，故需要两个士兵。
转化为二分图如下
最大匹配为2，最小路径为4-2=2。
#include <iostream>
using namespace std;
const int M=121;
bool g[M][M];
bool visit[M];
int link[M];
int n,k;
bool find(int i)
{
int j;
for(j=1;j<=n;j++)
{
if(g[i][j] && !visit[j])
{
visit[j]=true;
if(link[j]==0 || find(link[j]))
{
link[j]=i;
return true;
}
}
}
return false;
}
int main()
{
int i,j,res,c;
cin>>c;
while(c--)
{
cin>>n>>k;
memset(g,0,sizeof(g));
memset(link,0,sizeof(link));
res=0;
while(k--)
{
cin>>i>>j;
g[i][j]=true;
}
for(i=1;i<=n;i++)
{
memset(visit,0,sizeof(visit));
if(find(i))
res++;
}
cout<<n-res<<endl;
}
return 0;
}posted on 2011-09-13 18:49
大大木马 阅读(1364)
评论(1) 编辑 收藏 引用