Treasure Hunting

2 4
A.B.
***C
2 4
A#B.
***C

1
2

题目大意：iSea和他的朋友一块去寻宝，地图上显示了很多的金币，图中有字母‘A‘, ‘B‘ ... ‘Z‘, ‘a‘, ‘b‘ ... ‘z‘，表示他们每次的会合地点，开始位置在A，他朋友每次以最短的距离有一个会合地点走向下一个会合地点，iSea也必须走最短路，但是他可以选择走有金币的路，不过他只有一个单位的时间可以拿到金币，也就是说，每一次的会合过程，他只能带走一块金币。问：走到最后的会合地点，iSea最多能获得多少金币。输出-1的情况：1.存在的字母不连续。2.从A不能到达所有出现的字母。

建图过程：

首先分别记录字母和宝藏所在的位置，并统计和标号。

每个金币位置标号设为p1，每次会合的出发点设为p2，源点S，汇点T

可以建如下三类边：<u, v, w>分别表示一条边的起点，终点，边权

1. <S, p2, 1> 表示每一次出发最多拿到1枚金币

2. <p2, p1, 1> 表示每次出发可以拿到最短路径上的任意一个金币

3. <p1, T, 1> 表示从每个有金币的位置最多拿走一枚金币

如此建图，就能够保证流量最大时，iSea拿到的金币最多，当然，符合规则。

这题还有一关键点：建图的第2点。如何求得从路的起点到下一个目的地，最短路经过的宝藏地点（弄不好就会超时）。先bfs，把每个字母到达所有点的最短距离       vist[字母][到达的位置] 求出，如果 满足：vist[起始字母][宝藏位置]+vist[目标字母][同一宝藏的位置]＝＝vist[起始字母][目标字母的位置]，则说明这个宝藏在最短路上。

这题也可以用二分图最大匹配来做。相对于我上面的建图，去掉源点S，汇点T，即可。求得p2构成的X集合和p1构成的Y集合，题目上，每个出发点最多拿到一枚金币，求取最大金币数，正好符合二分图最大匹配的定义。

#include<stdio.h>
#include<string.h>
#include<queue>
#include<algorithm>
using namespace std;
#define captype int

const int MAXN = 100010;   //点的总数
const int MAXM = 400010;    //边的总数
const int INF = 1<<30;
struct EDG{
    int to,next;
    captype cap,flow;
} edg[MAXM];
int eid,head[MAXN];
int gap[MAXN];  //每种距离(或可认为是高度)点的个数
int dis[MAXN];  //每个点到终点eNode 的最短距离
int cur[MAXN];  //cur[u] 表示从u点出发可流经 cur[u] 号边
int pre[MAXN];

void init(){
    eid=0;
    memset(head,-1,sizeof(head));
}
//有向边 三个参数，无向边4个参数
void addEdg(int u,int v,captype c,captype rc=0){
    edg[eid].to=v; edg[eid].next=head[u];
    edg[eid].cap=c; edg[eid].flow=0; head[u]=eid++;

    edg[eid].to=u; edg[eid].next=head[v];
    edg[eid].cap=rc; edg[eid].flow=0; head[v]=eid++;
}
captype maxFlow_sap(int sNode,int eNode, int n){//n是包括源点和汇点的总点个数，这个一定要注意
    memset(gap,0,sizeof(gap));
    memset(dis,0,sizeof(dis));
    memcpy(cur,head,sizeof(head));
    pre[sNode] = -1;
    gap[0]=n;
    captype ans=0;  //最大流
    int u=sNode;
    while(dis[sNode]<n){   //判断从sNode点有没有流向下一个相邻的点
        if(u==eNode){   //找到一条可增流的路
            captype Min=INF ;
            int inser;
            for(int i=pre[u]; i!=-1; i=pre[edg[i^1].to])    //从这条可增流的路找到最多可增的流量Min
            if(Min>edg[i].cap-edg[i].flow){
                Min=edg[i].cap-edg[i].flow;
                inser=i;
            }
            for(int i=pre[u]; i!=-1; i=pre[edg[i^1].to]){
                edg[i].flow+=Min;
                edg[i^1].flow-=Min;  //可回流的边的流量
            }
            ans+=Min;
            u=edg[inser^1].to;
            continue;
        }
        bool flag = false;  //判断能否从u点出发可往相邻点流
        int v;
        for(int i=cur[u]; i!=-1; i=edg[i].next){
            v=edg[i].to;
            if(edg[i].cap-edg[i].flow>0 && dis[u]==dis[v]+1){
                flag=true;
                cur[u]=pre[v]=i;
                break;
            }
        }
        if(flag){
            u=v;
            continue;
        }
        //如果上面没有找到一个可流的相邻点，则改变出发点u的距离（也可认为是高度）为相邻可流点的最小距离+1
        int Mind= n;
        for(int i=head[u]; i!=-1; i=edg[i].next)
        if(edg[i].cap-edg[i].flow>0 && Mind>dis[edg[i].to]){
            Mind=dis[edg[i].to];
            cur[u]=i;
        }
        gap[dis[u]]--;
        if(gap[dis[u]]==0) return ans;  //当dis[u]这种距离的点没有了，也就不可能从源点出发找到一条增广流路径
                                        //因为汇点到当前点的距离只有一种，那么从源点到汇点必然经过当前点，然而当前点又没能找到可流向的点，那么必然断流
        dis[u]=Mind+1;//如果找到一个可流的相邻点，则距离为相邻点距离+1，如果找不到，则为n+1
        gap[dis[u]]++;
        if(u!=sNode) u=edg[pre[u]^1].to;  //退一条边
    }
    return ans;
}

int vist[55][10005] , dir[4][2]={1,0,-1,0,0,1,0,-1} ;
char mapt[105][105];
void bfs(int s,int frome,int R,int C){
    queue<int>q;
    int  x,y ;
    
    vist[s][frome]=0;
    q.push(frome);
    while(!q.empty()){
        int pre= q.front(); q.pop();
        x=pre/C;
        y=pre%C;
        for(int e=0; e<4; e++){
            int tx=x+dir[e][0];
            int ty=y+dir[e][1];
            int now=tx*C+ty;
            if(tx>=0&&tx<R&&ty>=0&&ty<C&&vist[s][now]==-1&&mapt[tx][ty]!='#'){
                vist[s][now]=vist[s][pre]+1;
                q.push(now);
            }
        }
    }
}

int main(){
    int id[105][105] , idk , ch[100] , gold[10005] , gk , R , C;

    while(scanf("%d%d",&R,&C)>0){
            
        for(int i=0; i<R; i++)
            scanf("%s",mapt[i]);
            
        idk = gk = 0 ;
        memset(ch,-1,sizeof(ch));
        for(int i=0; i<R; i++)
            for(int j=0; j<C; j++)
                if(mapt[i][j]=='*')
                   id[i][j]=++idk , gold[gk++]=i*C+j;
                else if(mapt[i][j]>='A'&&mapt[i][j]<='Z')
                   id[i][j]=++idk , ch[mapt[i][j]-'A']=i*C+j;
                else if(mapt[i][j]>='a'&&mapt[i][j]<='z')
                   id[i][j]=++idk , ch[mapt[i][j]-'a'+26]=i*C+j;


        int  ans = 0 ,sNode=0, eNode= idk+1;
        
        //--------------------------------建图-------------------------------------------
        init();
        for(int i=0; i<R; i++)
            for(int j=0; j<C; j++)
                if(mapt[i][j]>='A'&&mapt[i][j]<='Z'||mapt[i][j]>='a'&&mapt[i][j]<='z')
                    addEdg(sNode , id[i][j] , 1);   //源点与目的地建一条容量为 1 的边
                else if(mapt[i][j]=='*'){
                    addEdg(id[i][j] , eNode , 1);   //宝藏与汇点建一条容量为 1 的边
                }
        int i ,j=51 , frome , to ;

        while(ch[j]==-1&&j>=0)j--; j++;
        memset(vist,-1,sizeof(vist));

        for(i=0; i<j; i++) //先计算出每个目的地能到达的位置的最短距离
            if(ch[i]!=-1)
                bfs(i,ch[i],R,C);
            else{
                ans=-1; break;
            }
        if(ans==-1){
            printf("-1\n"); continue;
        }
        for(i=0; i<j-1; i++){
            frome = ch[i];
            to = ch[i+1];
            if(vist[i][to]==-1){
                ans = -1; break;
            }
            for(int e=0; e<gk; e++)
                if(vist[i][gold[e]]+vist[i+1][gold[e]]==vist[i][to])
                    addEdg(id[frome/C][frome%C] , id[gold[e]/C][gold[e]%C] , 1);   //每个目的地的起始位 与 最短路上的每个宝藏建一条容量为 1 的边
        }
        //-----------------------------------------------------------------------------
        
        if(ans==0){
            ans = maxFlow_sap(sNode,eNode,eNode+1);
        }
        printf("%d\n",ans);
    }
}

HDU 3468 Treasure Hunting (最大流SAP)经典（看似广搜实则最大流）

原文：http://blog.csdn.net/u010372095/article/details/46550357