HDOJ 3469 - Treasure Hunting BFS+二分图最大匹配...深入理解二分图最大匹配..

HDOJ 3469 - Treasure Hunting BFS+二分图最大匹配...深入理解二分图最大匹配..

题意:

iSea和他朋友一起来到一个迷宫中...每次他们会从一个集合点到达另一个集合点(集合点按顺序A~Z~a~z..最多52个)...在每两个集合点间必须走最短的路径(当然可能有多条)..iSea可以最多在两个集合点间的最短路径上拿一个宝藏..每个宝藏只能被拿一次....问能否完成所有的路径..不行输出-1..否则输出iSea能拿到的最多的宝藏个数..

题解:

可见在最终的答案中..一个宝藏至多属于一条线段上...于是想到用宝藏和线段来做匹配...宝藏作为一侧..两两集合点的最短路径作为另一侧...来做最大匹配..那么关键就是构边了..什么时候某个宝藏可以和一条路劲相连呢?这个宝藏必定属于某两个集合点的最短路径上...所以枚举集合点,,每次用BFS找出图中点到当前起点的最短距离..图中点到当前终点的最短距离..若有一个宝藏的两者之和等于起点到终点的最短距离..那么这个宝藏就与这条路径的标号做边...

总结:

这类问题的特点是一个集合中的某个元素至多匹配另一个集合中的一个元素...问最多的数量...其实也很裸了...

Program:

#include#include#include#include#include#include#include#define ll long long#define esp 1e-5#define MAXN 10005#define MAXM 5000005#define oo 1000007using namespace std; struct node{ int y,next;}line[MAXM];int Lnum,_next[MAXN],match[MAXN],way[4][2]={{1,0},{-1,0},{0,1},{0,-1}},dis[2][MAXN];bool had[105],used[MAXN];char s[105][105];void addline(int x,int y){ line[++Lnum].next=_next[x],_next[x]=Lnum,line[Lnum].y=y;}int BFS(int t,int R,int C,int tp){ int x,y,k,h; char c; queue Q; memset(dis[tp],0x2f,sizeof(dis[tp])); while (!Q.empty()) Q.pop(); if (t<26) c='A'+t; else c='a'+t-26; for (y=0;y=R || xx>=C) continue; if (s[yy][xx]=='#' || dis[tp][yy*C+xx]oo) return false; for (y=0;y='A' && s[i][j]<='Z' || s[i][j]>='a' && s[i][j]<='z') { if (s[i][j]>='A' && s[i][j]<='Z') x=s[i][j]-'A'; else x=s[i][j]-'a'+26; had[x]=true; num=max(num,x+1); } if (!build(R,C,num)) { printf("-1\n"); continue; } printf("%d\n",getmax(num-1)); } return 0; }

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。