HDU 3468 BFS+二分匹配 - c++编程基础

开始建图打搓了，参考了大牛的题解打的版本比较清爽，后来改的基本雷同了http://www.cnblogs.com/woaishizhan/archive/2013/04/08/3008719. html

题意：给定n，m表示下面地图大小

.表示空地 #表示墙 *表示黄金

行走的路线是A->Z->a->z

规则，必须从字母依次走最短路到下一个字母（字母必须连续走，如果走不到下一个字母或者地图上不存在下一个字母则输出-1）

每次走到下一个字母可以取走路途上的一个黄金，问最多能取走几个黄金

思路：走到最后一个字母就结束了，所以希望从每个字母走出来都能得到一个黄金，所以是二分匹配

把起点字母作为X集，黄金作为Y集，映射条件是黄金在字母间行走的最短路上

然后这里用BFS寻找路径建图

最后套个二分匹配的模版

#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#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];  
vectorG[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));  
    queueq;  
  
    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