DLKKILL

DLKKILL's world

POJ - 3041 - Cable master (二分图匹配入门,最小顶点覆盖)

题目链接:POJ – 1064

题目大意:

有一个N*N的图,图中一些点有障碍物,有一种武器,一次可以摧毁一行或者一列的障碍物,

问最少需要多少次,能把所有障碍物清除干净。

题目分析:

对于每个坐标点,建立一个行对应列的边,然后进行二分图匹配。

已知最大匹配数=最小顶点覆盖(最小顶点覆盖要求用最少的点(X或Y中都行),让每条边都至少和其中一个点关联

这样,在二分图中关联的边及原图中的障碍物,二分图中的点集即代表行和列。

求出最小顶点覆盖即可。

给出代码:

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
using namespace std;
const int maxn=1000+10;
int link[maxn];
int g[maxn][maxn];
int vist[maxn];
int n,k;
bool dfs(int x)
{
for(int i=1;i<=n;i++)
{
if(!vist[i]&&g[x][i])
{
vist[i]=1;
if(!link[i]||dfs(link[i]))
{
link[i]=x;
return true;
}
}
}
return false;
}
int research()
{   
    int ans=0;
memset(link,0,sizeof(link));
for(int i=1;i<=n;i++)
{   
memset(vist,0,sizeof(vist));
if(dfs(i))
ans++;
}
return ans;
}
int main()
{
   	cin>>n>>k;
for(int i=0;i<k;i++)
{
int a,b;
cin>>a>>b;
g[a][b]=1;
}
int t=research();
cout<<t<<endl;
//system("pause");
return 0;
}

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注