首页 > 代码库 > HDU 3360-National Treasures(最小点覆盖+奇偶匹配)
HDU 3360-National Treasures(最小点覆盖+奇偶匹配)
/******************************************************* 题意: 现在有一个n*m的博物馆g,每一个g[i][j]要不是一个<=2^12 的数,要不就是-1。 如果这个点是-1,表示这个点有一个守卫 否则就是以g[i][j]为关键字规则的宝物。 具体规则是: 现在有12个被编号的点(题目中给出了图片),然后把g[i][j]表示成一个12位二进制数 ,从低位到高位(右到左)依次为1~12,如果某位i上是1,就表示在编号 为i的相对位置放置一个守卫的话,这个宝物就能被保护了 守卫可以移走一个宝物自己代替那个格子,但不允许仅仅移走宝物 问最少需要再额外添加几个守卫使得未被移走的宝物都被保护 思路: 从图片中可看出,编号相对位置的都是马步位置和相邻位置,也就是说 其i+j的奇偶性必定与宝物的i+j的奇偶性不同,显然想到奇偶匹配 以奇点为集合A,偶点为集合B,A->B建边,如果中心点(i,j)的关键位置中 包含相对位置(x,y)点,那么就g[(i-1)*m+j].push_back((x-1)*m+y); 要注意如果中心点(i,j)的关键位置不包含(x,y)而(x,y)的关键位置包含(i,j) 也建立一条以上的边。 如果遇到关键位置上已经有守卫了,即mp[x][y] == -1,那就不要加边了(因为 最后求的是最小点覆盖,不加边就不需要考虑覆盖这条边了) 最后求最小点覆盖就行了 ********************************************************/ //#pragma comment(linker, "/STACK:1024000000,1024000000") #include "iostream" #include "cstring" #include "algorithm" #include "cmath" #include "cstdio" #include "sstream" #include "queue" #include "vector" #include "list" #include "string" #include "stack" #include "cstdlib" #include "deque" #include "fstream" #include "map" #include "set" #define lson(x) (x<<1) #define rson(x) (x<<1|1) #define MID(x,y) ((x+y)>>1) #define FR (freopen("in.txt","r",stdin)) #define clr(a,b) memset(a,b,sizeof(a)) #define lowbit(t) (t&-t) #define PI acos(-1.0) #define mkp make_pair using namespace std; typedef long long LL; const int MAXN = 2500+100; const int inf = 522133279; const int mod = 1000000007; int cx[MAXN],cy[MAXN]; int vis[MAXN]; vector<int> g[MAXN]; int mp[100][100]; int n,m; 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 duicheng[] = {4,5,6,7,0,1,2,3,10,11,8,9}; int path(int u) { for(int i = 0 ; i < g[u].size() ; i++) { int v = g[u][i]; if(!vis[v]) { vis[v]=1; if(cy[v] == -1 || path(cy[v])) { cx[u]=v; cy[v]=u; return 1; } } } return 0; } int maxMatch() { int res=0; clr(cx,-1); clr(cy,-1); for(int i = 1 ; i <= n*m ; i++) { if(cx[i] == -1) { clr(vis,0); res += path(i); } } return res; } bool border(int x , int y) { return (x>=1&&x<=n)&&(y>=1&&y<=m); } int main() { int ka=0; while(~scanf("%d%d",&n,&m),n+m) { for(int i = 0 ; i < MAXN ; i++) g[i].clear(); for(int i = 1 ; i <= n ; i++) for(int j = 1 ; j <= m ; j++) scanf("%d",&mp[i][j]); for(int i =1 ; i <= n ; i++) for(int j = 1 ; j <= m ; j++) { if((i+j)%2 && mp[i][j]!=-1) //对于奇点建边 { for(int k = 0 ; k < 12 ; k++) { int x = i+dir[k][0]; int y = j+dir[k][1]; if(!border(x,y) || mp[x][y] == -1) continue; if((1<<k)&mp[i][j]) g[(i-1)*m+j].push_back((x-1)*m+y); if((1<<duicheng[k]) & mp[x][y]) g[(i-1)*m+j].push_back((x-1)*m+y); } } } printf("%d. %d\n",++ka,maxMatch()); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。