本文主要是介绍HDU 3468 Treasure Hunting dijkstra+网络流解决的二分匹配，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：有最多52个点，他们分布在地图的一个地方，然后他们有先后的顺序，要按照这个顺序从第一个走到最后一个，在走每一段路的时候必须要是最短路，如果路上有金子，那么他就可以捡起一个金子，但是每一小段路只可以最多捡1个金子，问一个人从第一个点到最后一个点可以获得的最大金子数量。
想法：这是一个好题，主要考察预处理图信息的能力，代码有一点长吧。由于给的是矩阵图，我们可以把每一个点的决定信息--行列二维坐标，更换成数字一维坐标1~n*m。先保存每个路段端点的坐标和金子的坐标，对于每一个端点用一遍单源最短路（dij），我们可以知道假设dis[i][j]为i到j的最短距离，那么点x为最短路上的点的充要条件是：dis[i][k]+dis[k][j]=dis[i][j]。用反正法可以证明。这样图就预处理完了，那么每一个端点可以有一些金子的选择，这时就是二分匹配了。看最多可以匹配多少组，这就是答案。这里二分匹配我是用网络流写的，其他的也行。
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
#define inf 0x7fffffff
using namespace std;
const int nodes=10000+500;
const int edges=100000+500;
char map[105][105];
int dis[100][11000],vis[105][105],pos[105*105],gold[10000+5],cntp,cntg;
int dir[4][2]={0,1,1,0,0,-1,-1,0};
int n,m,s,t;
struct node
{int v,next,flow;
}e[edges];
int head[nodes],cnt,cur[nodes];
class Dinic
{ public: int spath() { queue<int>q; while(!q.empty()) q.pop(); memset(Dis,-1,sizeof(Dis)); Dis[s]=0; q.push(s); while(!q.empty()) { int u=q.front(); q.pop(); for(int i=head[u];i+1;i=e[i].next) { int v=e[i].v; if(Dis[v]==-1&&e[i].flow>0) { Dis[v]=Dis[u]+1; q.push(v); } } } return Dis[t]!=-1; } int Min(int a,int b) { if(a<b) return a; return b; } int dfs(int u,int flow) { int cost=0; if(u==t) return flow; for(int &i=cur[u];i+1;i=e[i].next) { int v=e[i].v; if(Dis[v]==Dis[u]+1&&e[i].flow>0) { int min=dfs(v,Min(e[i].flow,flow-cost)); if(min>0) { e[i].flow-=min; e[i^1].flow+=min; cost+=min; if(cost==flow) break; } else Dis[v]=-1; } } return cost; } int result() { int res=0; while(spath()) { for(int i=0;i<=t;i++) cur[i]=head[i]; res+=dfs(s,inf); } return res; } private: int Dis[nodes];
}dinic;
void Init()
{memset(head,-1,sizeof(head));memset(map,'\0',sizeof(map));cnt=0;
}
void add(int a,int b,int c)
{e[cnt].v=b;e[cnt].flow=c;e[cnt].next=head[a];head[a]=cnt++;e[cnt].v=a;e[cnt].flow=0;e[cnt].next=head[b];head[b]=cnt++;
}
void bfs(int k)
{queue<int>q;while(!q.empty()) q.pop();memset(vis,0,sizeof(vis));memset(dis[k],inf,sizeof(dis[k]));for(int i=0;i<=n*m;i++)dis[k][i]=inf;int ss=pos[k];vis[ss/m][ss%m]=1;dis[k][ss]=0;q.push(ss);while(!q.empty()){int u=q.front();q.pop();int x=u/m;int y=u%m;for(int i=0;i<4;i++){int xx=x+dir[i][0];int yy=y+dir[i][1];if(vis[xx][yy]) continue;if(xx<0||xx>=n||yy<0||yy>=m) continue;if(map[xx][yy]=='#') continue;vis[xx][yy]=1;dis[k][xx*m+yy]=dis[k][x*m+y]+1;q.push(xx*m+yy);}}
}
int trans(char x)
{if(x>='A'&&x<='Z'){return x-'A';}else{return x-'a'+26;}
}
int main()
{while(~scanf("%d%d",&n,&m)){Init();for(int i=0;i<n;i++){scanf("%s",map[i]);}cntp=0;cntg=0;for(int i=0;i<n;i++){for(int j=0;j<m;j++){if((map[i][j]>='A'&&map[i][j]<='Z')||(map[i][j]>='a'&&map[i][j]<='z')){pos[trans(map[i][j])]=i*m+j;cntp++;}else if(map[i][j]=='*'){gold[cntg++]=i*m+j;}}}for(int i=0;i<cntp;i++){bfs(i);}int noway=0;for(int i=1;i<cntp;i++){for(int j=0;j<cntg;j++){if(dis[i][gold[j]]+dis[i-1][gold[j]]==dis[i-1][pos[i]]){add(i,cntp+j,1);}if(dis[i-1][pos[i]]==inf){noway=1;}}}if(noway){printf("-1\n");continue;}s=0;t=cntp+cntg;for(int i=1;i<cntp;i++){add(s,i,1);}for(int i=0;i<cntg;i++){add(cntp+i,t,1);}printf("%d\n",dinic.result());} return 0;
} 这篇关于HDU 3468 Treasure Hunting dijkstra+网络流解决的二分匹配的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
