好贷网好贷款

HDU 3468 BFS + 二分匹配

发布时间:2016-12-5 16:35:48 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"HDU 3468 BFS + 二分匹配",主要涉及到HDU 3468 BFS + 二分匹配方面的内容,对于HDU 3468 BFS + 二分匹配感兴趣的同学可以参考一下。

九野的博客,转载请注明出处 http://blog.csdn.net/acmmmm/article/details/10966383   题意:给定n,m表示下面地图大小 .表示空地 #表示墙 *表示黄金 行走的路线是A->Z || a->z 规则,必须从字母依次走最短路到下一个字母(字母必须连续走,如果走不到下一个字母或者地图上不存在下一个字母则输出-1) 每次走到下一个字母可以取走路途上的一个黄金,问最多能取走几个黄金   思路:走到最后一个字母就结束了,所以希望从每个字母走出来都能得到一个黄金,所以是二分匹配 把起点字母作为X集, 黄金作为Y集, 映射条件是黄金在 字母间行走的最短路上 若黄金在最短路上 则满足: 起点到终点距离 = 黄金到起点距离 + 黄金到终点距离   然后这里用BFS寻找路径建图 最后套个二分匹配的模版   #include<stdio.h> #include<algorithm> #include<iostream> #include<set> #include<math.h> #include<string.h> #include<queue> #include<vector> #define N 105 #define inf 999999999 using namespace std; int n,M; int road[N],p[N*N],gold[N*N],num,pn;//road 表示字母在p中的编号,p是字母的坐标(一维化) int dis[N][N*N];//dis[a][b] 表示离散化的字母点a到 一维化的坐标b的距离 char map[N][N]; vector<int>G[N]; int go[4][2]={1,0,0,1,-1,0,0,-1}; void bfs(int s){ bool vis[N*N]; memset(vis,0,sizeof(vis)); queue<int>q; memset(dis[s],-1,sizeof(dis[s])); dis[s][p[s]]=0; q.push(p[s]); vis[p[s]]=1; while(!q.empty()) { int t=q.front(); int x=t/M,y=t%M; q.pop() ; for(int i=0;i<4;i++) { int nowx=x+go[i][0],nowy=y+go[i][1]; int now=nowx*M+nowy; if(map[nowx][nowy]=='#')continue; if(nowx<0 || nowx>=n ||nowy<0||nowy>=M)continue; if(vis[now])continue; vis[now]=1; dis[s][now]=dis[s][t]+1; q.push(now); } } } int lef[N*N];//lef[v]表示右边点v 当前连接的点 bool T[N*N];//右边的点是否连过 bool match(int x) { for(int i=0;i<G[x].size();i++) { int v=G[x][i]; if(!T[v]) { T[v]=true; if(lef[v]==-1||match(lef[v])) { lef[v]=x; return true; } } } return false; } void solve() { int ans=0; memset(lef,-1,sizeof(lef)); for(int i=0;i<pn-1;i++)//左右点集匹配,左点集是 0-(pn-1) 右点集是G[左点].size() { memset(T,0,sizeof(T)); if(match(i))ans++; } printf("%d\n",ans); } int f(char c){ if('A'<=c && c<='Z')return c-'A'; else if('a'<=c && c<='z')return c-'a'+26; } int main(){ int i,j; while(~scanf("%d%d",&n,&M)){ pn=num=0; memset(road,-1,sizeof(road));//这句没有最后第二个案例过不了 for(i=0;i<n;i++) { scanf("%s",map[i]); for(j=0;j<M;j++) if(isalpha(map[i][j])) { p[pn]=i*M+j; road[f(map[i][j])]=pn; pn++; } else if(map[i][j]=='*') { gold[num++]=i*M+j; } } for(i=0;i<pn;i++)bfs(i),G[i].clear(); for(i=0;i<pn-1;i++) { if(road[i]==-1||road[i+1]==-1) break; if(dis[road[i]][p[road[i+1]]]==-1) break; } if(i!=pn-1){puts("-1");continue;} for(i=0;i<pn-1;i++) for(j=0;j<num;j++) { if(dis[road[i]][gold[j]]==-1 || dis[road[i+1]][gold[j]]==-1)continue;//j这点的黄金到不了字母点 if(dis[road[i]][gold[j]]+dis[road[i+1]][gold[j]]==dis[road[i]][p[road[i+1]]]) G[i].push_back(j); } solve(); } return 0; } /* 3 4 A#B. ***C .D.. 4 4 A#B. ***C .D.. ..E* 4 4 A#B. ***C .D.. .*E* 4 4 A#B. ***C .D#. .#E* 4 4 A#B. ***C .D#. .#E. 4 4 A#B. ***C .D## .#E. 4 4 A#B. ***C .D#* .#E. 4 4 a#b. ***c .d#* .#e. 4 4 A#B* *.*C ..D# E*.. ans; 3 3 4 4 3 -1 4 -1 4 */      

上一篇:对Java克隆方法的研究(二)
下一篇:linux流量限速工具tc简介

相关文章

相关评论