hdu 4619 Warm up 2_最大独立集

时间:2022-05-20 10:20:55

三个人整个下午都想不出这题

后来看题解,竟然用匈牙利算法的最大独立集,我顿时晕了。

题意:给竖着和横着的方块,除去重叠的,最多能留下几个方块

#include <cstdlib>
#include <iostream>
using namespace std;
#define N 1010
struct Point{
int x,y;
Point(){}
Point(int a,int b){x=a;y=b;}
bool operator==(const Point &a)const{
return x==a.x&&y==a.y;
}
}pn[N],pm[N];
int link[N],n,m;
bool vis[N],g[N][N];
bool judge(Point a,Point b){
if(a==b||Point(a.x+1,a.y)==b||Point(b.x,b.y+1)==a||Point(a.x+1,a.y)==Point(b.x,b.y+1))
return 1;
return 0;
}
bool dfs(int u){
int i;
for(i=0;i<m;i++){
if(!vis[i]&&g[u][i]){
vis[i]=1;
if(link[i]==-1||dfs(link[i])){
link[i]=u;
return 1;
}
}
}
return 0;
}
int main(int argc, char *argv[])
{
int i,j;
while(scanf("%d%d",&n,&m)&&m||n){
memset(g,0,sizeof(g));
for(i=0;i<n;i++)
scanf("%d%d",&pn[i].x,&pn[i].y);
for(i=0;i<m;i++)
scanf("%d%d",&pm[i].x,&pm[i].y);
for(i=0;i<n;i++)
for(j=0;j<m;j++)
if(judge(pn[i],pm[j]))
g[i][j]=1;
memset(link,-1,sizeof(link));
int sum=0;
for(i=0;i<n;i++){
memset(vis,0,sizeof(vis));
sum+=dfs(i);
}
printf("%d\n",n+m-sum);
}
//system("PAUSE");
return EXIT_SUCCESS;
}

hdu 4619 Warm up 2_最大独立集的更多相关文章

  1. HDU 4619 Warm up 2 最大独立集

    Warm up 2 题目连接: http://acm.hdu.edu.cn/showproblem.php?pid=4619 Description Some 1×2 dominoes are pla ...

  2. hdu 4619 Warm up 2(并查集)

    借用题解上的话,就是乱搞题.. 题意理解错了,其实是坐标系画错了,人家个坐标系,我给当矩阵画,真好反了.对于题目描述和数据不符的问题,果断相信数据了(这是有前车之鉴的hdu 4612 Warm up, ...

  3. hdu 4619 Warm up 2

    http://acm.hdu.edu.cn/showproblem.php?pid=4619 根据题意可知,每一个方格可能只被一个骨牌覆盖 可能被两个骨牌覆盖 也可能不被覆盖 有一个骨牌覆盖的方格(单 ...

  4. HDU 4619 Warm up 2(2013多校2 1009 二分匹配)

    Warm up 2 Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 65535/32768 K (Java/Others)Total S ...

  5. hdu 4619 Warm up 2 &lpar; 二分图最大匹配 &rpar;

    题目:Warm up 2 题意:有横竖两种方式放着的多米诺骨牌,相同方向的不可能重叠,但是横放和竖放             的牌可能重叠.移走重叠的牌使剩下的牌最多. 分析:二分图匹配:最大独立集= ...

  6. hdu 4619 Warm up 2 &lpar;二分匹配)

    题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4619 题意: 平面上有一些1×2的骨牌,每张骨牌要么水平放置,要么竖直放置,并且保证同方向放置的骨牌不 ...

  7. hdu 4619 Warm up 2 网络流 最小割

    题意:告诉你一些骨牌,然后骨牌的位置与横竖,这样求最多保留多少无覆盖的方格. 这样的话有人用二分匹配,因为两个必定去掉一个,我用的是最小割,因为保证横着和竖着不连通即可. #include <s ...

  8. hdu 4619 Warm up 2 二分图匹配

    题目链接 给两种长方形, 水平的和垂直的, 大小都为1*2, n个水平的, m个垂直的, 给出它们的坐标. 水平的和垂直的可以相互覆盖, 但是同种类型的没有覆盖. 去掉一些长方形, 使得剩下的全部都没 ...

  9. HDU 4619 Warm up 2 贪心或者二分图匹配

    给同一张横着的牌的所在的格子编同一样的号,这些格子对应x集合,给同一张竖着的牌所在的格子编同一样的号,对应y集合,同一个格子上既有横着的牌又有竖着的牌,那么就建一条边,有冲突就要拿走一张,结果是总的牌 ...

随机推荐

  1. js 字符串截取

    substr方法: text.substr(start[,length]); text:要提取子字符串的字符串或String对象.必选 start:子字符串的起始位置.以0开始索引.必选 length ...

  2. 可编译为 UNICODE 和 ANSI 版本的遍历目录树程序&lowbar;0&period;1

    路径暂时是写死的 编译两个版本的程序: g++  treeT.cpp -municode -D_UNICODE -o treeT_UNIg++  treeT.cpp -o treeT_ASC 为了观察 ...

  3. 移动设备优先viewport

    Bootstrap 3 的设计目标是移动设备优先,然后才是桌面设备.这实际上是一个非常及时的转变,因为现在越来越多的用户使用移动设备. 为了让 Bootstrap 开发的网站对移动设备友好,确保适当的 ...

  4. python 调用mysql存储过程返回结果集

    存储过程: delimiter | ),)) begin select * from tb_test where mid = imid and user = iuser; end; | delimit ...

  5. yum服务器设置

    转自:http://blog.chinaunix.net/uid-22141042-id-1789605.html 不得不说,RedHat的确很邪恶,如果我们直接用他自带的系统碟做YUM源的话,总是会 ...

  6. Ember&period;js demo5

    <!DOCTYPE html> <html> <head> <meta name="description" content=" ...

  7. Kooboo CMS 介绍

    Kooboo的定位是一个CMS,内容管理平台,从更严格意义上来说,它更应该网站快速开发平台.针对一般网站开发过程的分析和提炼,着重在解决网站的一般需求,提出一套快速开发网站的理念和方法.在这些理念和方 ...

  8. iOS 两种方法实现左右滑动出现侧边菜单栏 slide view

      现在很多的APP中都有slide view,左右滑动出现侧边菜单栏的功能,Weico这个应用就有. 网上有很多第三方的类库实现了这种效果,其实自己代码写的话也是很简单的,下面我将介绍两种方法实现s ...

  9. web实现QQ第三方登录

    开放平台-web实现QQ第三方登录   应用场景     web应用通过QQ登录授权实现第三方登录.   操作步骤     1  注册成为QQ互联平台开发者,http://connect.qq.com ...

  10. 软件project(六)——需求分析

           需求分析是软件开发期的第一个阶段,是关系到软件开发成败的关键步骤.需求分析的任务就是明白系统必须完毕那些工作,以下是对需求分析这一章做的简要总结. 导图: 解释说明:        我将 ...