HDU 4619 Warm up 2 (二分图最小覆盖集)
http://acm.hdu.edu.cn/showproblem.php?pid=4619
题意:
给你两种纸牌 ,一种水平放置共有n张,一种竖直放置共有m张。水平放置的纸牌占据点(x, y)和(x + 1 , y) , 竖直放置的纸牌占据点(x , y) 和 (x , y + 1)。水平放置的牌之间不会重叠,竖直放置的牌之间也不会重叠,但是水平放置的牌和竖直放置的牌之间可能会重叠。让你拿走一些牌,使剩下的牌之间不会重叠并且数量最多,输出剩余的最大牌数。
分析:
我们把所有水平的骨牌放到二分图左点集,竖直骨牌放在二分图右点集. 如果左(水平)骨牌i与右(竖直)骨牌j有重叠部分,那么就在左i与右j之间连一条无向边.
注意:一个坐标最多只有2个骨牌重叠,且这两个骨牌一定一个是水平的另一个是竖直的.
所以新的二分图中每条边都代表了一个重叠的坐标位置.我们必须在每个重叠的位置上选择拿掉水平骨牌或是竖直骨牌来使得所有骨牌不重叠.(其实就是在二分图的左边或右边选每条边的端点抛弃).
为了使得剩下的骨牌最多,我们移除的重叠骨牌必须最少,那么这个问题就是求二分图的最小覆盖集.(想想是不是)
最终n+m-最小覆盖集数= 剩下的骨牌最大数目.
AC代码:
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
const int maxn = 1000+10;
struct Max_Match
{
int n,m;
vector<int> g[maxn];
bool vis[maxn];
int left[maxn];
void init(int n,int m)
{
this->n=n;
this->m=m;
for(int i=1;i<=n;i++) g[i].clear();
memset(left,-1,sizeof(left));
}
bool match(int u)
{
for(int i=0;i<g[u].size();i++)
{
int v=g[u][i];
if(!vis[v])
{
vis[v]=true;
if(left[v]==-1 || match(left[v]))
{
left[v]=u;
return true;
}
}
}
return false;
}
int solve()
{
int ans=0;
for(int i=1;i<=n;i++)
{
memset(vis,0,sizeof(vis));
if(match(i)) ans++;
}
return ans;
}
}MM;
struct Node
{
int x1,y1;
int x2,y2;
Node(){}
Node(int x1,int y1,int x2,int y2):x1(x1),y1(y1),x2(x2),y2(y2){}
bool overlap(Node& rhs)//判断是否重叠
{
if(x1==rhs.x1 && y1==rhs.y1) return true;
else if(x1==rhs.x2 && y1==rhs.y2) return true;
else if(x2==rhs.x1 && y2==rhs.y1) return true;
else if(x2==rhs.x2 && y2==rhs.y2) return true;
return false;
}
}node1[maxn],node2[maxn];
int main()
{
int n,m;
while(scanf("%d%d",&n,&m)==2 && n)
{
MM.init(n,m);
for(int i=1;i<=n;i++)
{
int x,y;
scanf("%d%d",&x,&y);
node1[i]=Node(x,y,x+1,y);
}
for(int i=1;i<=m;i++)
{
int x,y;
scanf("%d%d",&x,&y);
node2[i]=Node(x,y,x,y+1);
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(node1[i].overlap(node2[j]))
MM.g[i].push_back(j);
printf("%d\n",n+m-MM.solve());
}
return 0;
}
分享到:
相关推荐
杭电ACM课件2014版之 (HDUACM201403版_06)并查集(最小生成树)
B HDU 5093 Battle ships题意给出一个n行m列的图,*代表海域,o代表冰水,#代表冰山,要想在海域中放置船,保证船与船之间不能相互看到,之间
(HDUACM2010版_06)并查集(最小生成树(HDUACM2010版_06)并查集(最小生成树(HDUACM2010版_06)并查集(最小生成树(HDUACM2010版_06)并查集(最小生成树
hdu2215 最简单的最小圆覆盖
2-sat---hdu3062,代码详尽,清晰,格式规范,亲测无误。
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
杭电ACMhdu1163
HDU1059的代码
hdu1001解题报告
hdu 1574 passed sorce
本人准备2020年保研机试时刷的题目(虽然最后机试取消了,...来自某中流985,在HDU和vjudge平台上大概刷了400道。本文件地图(excel表格)包含了绝大部分我刷过的题目,笔记中具有思路、代码、总结和心得。 大佬勿入!
HDU的一题........HDU DP动态规
hdu2101AC代码
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
二分图匹配实例代码及整理 1、匈牙利算法 HDU 1150 #include #include #include using namespace std; int m,n,k; int vis[105]; int mpt[105][105]; int use[105]; int hungary(int x) { for(int i=1;i<m;i++)...
搜索 dfs 解题代码 hdu1241
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)
ACM HDU题目分类,我自己总结的大概只有十来个吧