Treasure Hunting HDU - 3468

题意：

　　输入一个n行m列的图

　　每次按字母顺序走最短路， 从一个字母走到下一个字母的过程中，只能拿走一个金子，求走完当前图中所有的字母后能拿到的金子的最大值

解析：

　　bfs求最短路

　　对于一个金子如果 dis1[i] + dis2[i] == dis1[next] 那么就代表着这个金子 在这条最短路上 可以拿 那么从上一个 字母 到当前节点连一条边 权值为1

　　会了吧。。。

#include <iostream>

#include <cstdio>

#include <sstream>

#include <cstring>

#include <map>

#include <cctype>

#include <set>

#include <vector>

#include <stack>

#include <queue>

#include <algorithm>

#include <cmath>

#include <bitset>

#define rap(i, a, n) for(int i=a; i<=n; i++)

#define rep(i, a, n) for(int i=a; i<n; i++)

#define lap(i, a, n) for(int i=n; i>=a; i--)

#define lep(i, a, n) for(int i=n; i>a; i--)

#define rd(a) scanf("%d", &a)

#define rlld(a) scanf("%lld", &a)

#define rc(a) scanf("%c", &a)

#define rs(a) scanf("%s", a)

#define pd(a) printf("%d\n", a);

#define plld(a) printf("%lld\n", a);

#define pc(a) printf("%c\n", a);

#define ps(a) printf("%s\n", a);

#define MOD 2018

#define LL long long

#define ULL unsigned long long

#define Pair pair<int, int>

#define mem(a, b) memset(a, b, sizeof(a))

#define _  ios_base::sync_with_stdio(0),cin.tie(0)

//freopen("1.txt", "r", stdin);

using namespace std;

const int maxn = , INF = 0x7fffffff, LL_INF = 0x7fffffffffffffff;

int n, m, s, t;

int d[maxn], vis[maxn];

int head[maxn], cur[maxn], cnt, dis1[maxn], dis2[maxn];

char str[][];

int dis[][] = {{, }, {, -}, {, }, {-, }};

vector<int> g;

struct edge

{

    int u, v, c, next;

}Edge[maxn];

void add_(int u, int v, int c)

{

    Edge[cnt].u = u;

    Edge[cnt].v = v;

    Edge[cnt].c = c;

    Edge[cnt].next = head[u];

    head[u] = cnt++;

}

void add(int u, int v, int c)

{

    add_(u, v, c);

    add_(v, u, );

}

struct node

{

    int alpha, idx;

    bool operator < (const node &a) const{

        return alpha < a.alpha;

    }

}Node[maxn];

void bfs1(int s)

{

    for(int i = ; i < maxn; i++) d[i] = INF;

    queue<int> Q;

    mem(vis, );

    Q.push(s);

    vis[s] = ;

    d[s] = ;

    while(!Q.empty())

    {

        int u = Q.front(); Q.pop();

        for(int i = ; i < ; i++)

        {

            int v = u + dis[i][] * m + dis[i][];

            if(u % m ==  && i ==  || (u - ) % m ==  && i == ) continue;

            if(v <  || v > n * m || vis[v] || str[v / m + ][v % m] == '#') continue;

            d[v] = d[u] + ;

            vis[v] = ;

            Q.push(v);

        }

    }

}

bool bfs2()

{

    mem(d, );

    queue<int> Q;

    Q.push();

    d[] = ;

    while(!Q.empty())

    {

        int u = Q.front(); Q.pop();

        for(int i = head[u]; i != -; i = Edge[i].next)

        {

            edge e = Edge[i];

            if(!d[e.v] && e.c > )

            {

                d[e.v] = d[u] + ;

                Q.push(e.v);

                if(e.v == t) return ;

            }

        }

    }

    return d[t] != ;

}

int dfs(int u, int cap)

{

    int ret = ;

    if(u == t || cap == )

        return cap;

    for(int &i = cur[u]; i != -; i = Edge[i].next)

    {

        edge e = Edge[i];

        if(d[e.v] == d[u] +  && e.c > )

        {

            int V = dfs(e.v, min(e.c, cap));

            Edge[i].c -= V;

            Edge[i ^ ].c += V;

            ret += V;

            cap -= V;

            if(cap == ) break;

        }

    }

    if(cap > ) d[u] = -;

    return ret;

}

int Dinic()

{

    mem(d, );

    int ans = ;

    while(bfs2())

    {

        memcpy(cur, head, sizeof(head));

        ans += dfs(, INF);

    }

    return ans;

}

int main()

{

    while(~scanf("%d%d", &n, &m))

    {

        g.clear();

        t = ;

        mem(head, -);

        cnt = ;

        int ans = ;

        for(int i = ; i <= n; i++)

        {

            rs(str[i] + );

            for(int j = ; j <= m; j++)

            {

                if(str[i][j] >= 'A' && str[i][j] <= 'z')

                    Node[ans].alpha = str[i][j], Node[ans++].idx = (i - ) * m + j;

                if(str[i][j] == '*')

                    g.push_back((i - ) * m + j), add((i - ) * m + j + , , );

            }

        }

        sort(Node, Node + ans);

        int num = , flag = ;

        for(int i = ; i < ans - ; i++)

        {

            ++num;

            bfs1(Node[i].idx);

            memcpy(dis1, d, sizeof(d));

            if(dis1[Node[i + ].idx] == INF)

            {

                flag = ;

                break;

            }

            bfs1(Node[i + ].idx);

            memcpy(dis2, d, sizeof(d));

            for(int j = ; j < g.size(); j++)

                if(dis1[g[j]] + dis2[g[j]] == dis1[Node[i + ].idx])

                    add(num, g[j] + , );

        }

        if(flag == )

        {

            cout << "-1" << endl;

            continue;

        }

        for(int i = ; i <= ; i++)

            add(, i, );

        cout << Dinic() << endl;

    }

    return ;

}