这道题向了我好久,看了题解也是一时没想通。
二分图的建模个人感觉挺不容易的,可能是刚学的原因吧~
题意:大厅每个位置都有一个文物或者一个守卫,
文物是安全的前提是:关键位置上必须有一个守卫,或者文物本身的位置上有一个守卫。
求保证每个文物是安全的守卫的最少数量。
分析:由于文物的关键位置在文物的马步或者相邻的位置上,所以此问题可看成二分图。
以(0,0)位置出发,格子可以分成与(0,0)点距离为奇数的点和偶数的点。
之后求二分图的最大匹配即可。
#include<stdio.h>
#include<string.h>
#include<vector>
using namespace std;
vector<int>map[2550];//建邻接表
int r,c,value[55][55],pre[2550];
int dir[12][2]={{-1,-2},{-2,-1},{-2,1},{-1,2},{1,2},{2,1},{2,-1},{1,-2},{-1,0},{0,1},{1,0},{0,-1}};
int rev[12]={4,5,6,7,0,1,2,3,10,11,8,9};
int judge[12]=
{
0x001,0x002,0x004,0x008,
0x010,0x020,0x040,0x080,
0x100,0x200,0x400,0x800
};
bool flag[2550];
int find(int cur)
{
int i,j;
for(i=0;i<map[cur].size();i++)
{
int k=map[cur][i];
if(!flag[k])
{
flag[k]=1;
if(!pre[k]||find(pre[k]))
{
pre[k]=cur;
return 1;
}
}
}
return 0;
}
void make_map()
{
int i,j,k;
for(i=0;i<r*c;i++)map[i].clear();
for(i=0;i<r;i++)
for(j=0;j<c;j++)
{
int s=i*c+j;
if((i+j)%2==0)continue;
if(value[i][j]==-1)continue;
for(k=0;k<12;k++)
{
int x=i+dir[k][0];
int y=j+dir[k][1];
int ss=x*c+y;
if(x<0||x>=r||y<0||y>=c)continue;
if(value[x][y]==-1)continue;
if(judge[k]&value[i][j])
map[s].push_back(ss);
else if(judge[rev[k]]&value[x][y])
map[s].push_back(ss);
}
}
}
int main()
{
int i,j,k=1,a,b;
while(scanf("%d%d",&r,&c)!=-1&&(r+c))
{
memset(pre,0,sizeof(pre));
int ans=0;
for(i=0;i<r;i++)
for(j=0;j<c;j++)
make_map();
int sum=0,s;
for(i=0;i<r;i++)
for(j=0;j<c;j++)
{
if(value[i][j]!=-1&&((i+j)&1))//距离为奇数且没有守卫的点进行匹配
{
memset(flag,0,sizeof(flag));
s=i*c+j;
sum+=find(s);
}
}
printf("%d. %d\n",k++,sum);
}
return 0;
}
分享到:
相关推荐
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
2019 Multi-University Training Contest 4(2019hdu多校第六场数据与标程)
ACM HDU 2000->2099 解题报告 ACM HDU 2000->2099 解题报告 ACM HDU 2000->2099 解题报告
此程序为hdu的acm2010题,就是解决水仙花数问题
杭电hdu acm资料所用杭电的acm题
包含实验内容:对应实验要求上的1/2/3/5实验,分别为setName/setNice,petree输出进程,模拟shell,进程通信,文件系统。包含全部实验源代码和详尽的word实验报告。同时包含在线PTA编程题目:进程模拟,模拟进程调度...
HDU一部分题目原码,大部分是可运行的,可能有几题不完整
杭电 hdu acm 第1084题的解法,ac过了,是一位学长教我的.内有一些中文说明.
(HDUACM2010版_08)母函数(HDUACM2010版_08)母函数(HDUACM2010版_08)母函数(HDUACM2010版_08)母函数(HDUACM2010版_08)母函数(HDUACM2010版_08)母函数
hdu 1005.比较简单的一道题,有兴趣的可以看看。
ACM HDU题目分类,我自己总结的大概只有十来个吧
hdu-acm源代码(上百题)hdu-acm源代码、hdu-acm源代码hdu-acm源代码
压缩包包含十份报告,已经通过验收,实验内容:交换机、生成树、静态路由、NAT等完全根据教材实验要求
100道 acm C语言 hdu 解题报告
ACM hdu 代码大全3000例,hdu已经AC的3000例代码,部分代码有详细解析
HDU1059的代码
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
HDU2013暑期多校联合训练第一场0723-解题报告和标程
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)
一个十分简单的程序,能够ac杭电hdu的第2050题,无注释,简单明了