首页 > 其他 > 详细

POJ3041-最小覆盖问题

时间:2020-07-02 22:07:41      阅读:63      评论:0      收藏:0      [点我收藏+]

POJ3041
这道题正解比较难以想到。
我们发现每次覆盖的只是一条线上的所有点。那么我们可以把它想象成一个二分图,两个集合分别是横轴和纵轴。
想一想,这实际上是不是就是x轴轴和纵轴的最大匹配?
于是这就变成了一个板子匈牙利算法题目。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<ctype.h>
#define R register
using namespace std;
inline int read()
{
	int x=0,w=0;char c=getchar();
	while(!isdigit(c))w|=c==‘-‘,c=getchar();
	while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
	return w?-x:x;
}
const int maxn=505,maxm=10005;
int n,m;
int mapp[maxn][maxn];
bool vis[maxn];
int match[maxn];
bool find(int x)
{
	for(R int i=1;i<=n;i++)
		if(mapp[x][i] and vis[i]==0)
		{
			vis[i]=1;
			if(match[i]==0 || find(match[i]))
			{
				match[i]=x;
				return 1;
			}
		}
	return 0;
}
int main()
{
	n=read(),m=read();
	for(R int i=1;i<=m;i++)mapp[read()][read()]=1;
	int ans=0;
	for(R int i=1;i<=n;i++)
	{
		memset(vis,0,sizeof vis);
		if(find(i))ans++;
	}
	printf("%d",ans);
	return 0;
}

POJ3041-最小覆盖问题

原文:https://www.cnblogs.com/BrotherHood/p/13227384.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!