LightOJ 1243 Guardian Knights 费用流

题目：http://www.lightoj.com/volume_showproblem.php?problem=1243

题意：在一个n * n的矩阵中有k个骑士和m个磨坊，然后让骑士走到磨坊上保卫磨坊，话费为所走的路程，一个骑士可以照看多个磨坊，花费为到它们的距离之和，一个磨坊也可以由多个骑士保卫。求最小花费

思路：首先从源点向骑士连边，容量为骑士可以保卫的个数，从磨坊向汇点连边，容量为1，虽然一个磨坊可以由多个骑士保卫，但明显用一个骑士花费最小。然后对于骑士和磨坊之间的连边，每次都bfs一次，求花费然后连边。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <map>
using namespace std;

const int N = 110;
const int INF = 0x3f3f3f3f;
typedef pair<int, int> P;
struct edge
{
    int st, to, cost, cap, next;
} g[N*N*2];
char str[N][N];
int cnt, head[N*2];
int dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0};
int dis[N*2], pre[N*2], arr[N];
int idx[N][N];
bool vis[N*2];
int cas = 0;
void add_edge(int v, int u, int cost, int cap)
{
    g[cnt].st = v, g[cnt].to = u, g[cnt].cost = cost, g[cnt].cap = cap, g[cnt].next = head[v], head[v] = cnt++;
    g[cnt].st = u, g[cnt].to = v, g[cnt].cost = -cost, g[cnt].cap = 0, g[cnt].next = head[u], head[u] = cnt++;
}
void spfa(int s, int t)
{
    memset(dis, 0x3f, sizeof dis);
    memset(vis, 0, sizeof vis);
    memset(pre, -1, sizeof pre);
    queue<int> que;
    que.push(s);
    dis[s] = 0, vis[s] = true;
    while(! que.empty())
    {
        int v = que.front();
        que.pop();
        vis[v] = false;
        for(int i = head[v]; i != -1; i = g[i].next)
        {
            int u = g[i].to;
            if(g[i].cap > 0 && dis[u] > dis[v] + g[i].cost)
            {
                dis[u] = dis[v] + g[i].cost;
                pre[u] = i;
                if(! vis[u])
                    que.push(u), vis[u] = true;
            }
        }
    }
}
int cost_flow(int s, int t, int flow)
{
    int res = 0;
    while(flow > 0)
    {
        spfa(s, t);
        if(dis[t] == INF) return -1;
        int d = flow;
        for(int i = pre[t]; i != -1; i = pre[g[i].st])
            d = min(d, g[i].cap);
        flow -= d;
        res += d * dis[t];
        for(int i = pre[t]; i != -1; i = pre[g[i].st])
            g[i].cap -=d, g[i^1].cap += d;
    }
    return res;
}
void bfs(int x, int y, int n, int k)
{
    queue<P> que;
    int dist[N][N];
    memset(dist, 0x3f, sizeof dist);
    que.push(P(x, y));
    dist[x][y] = 0;
    while(! que.empty())
    {
        P p = que.front();
        que.pop();
        for(int i = 0; i < 4; i++)
        {
            int nx = p.first + dx[i], ny = p.second + dy[i];
            if(nx >= 0 && nx < n && ny >= 0 && ny < n && dist[nx][ny] == INF && str[nx][ny] != '#')
            {
                dist[nx][ny] = dist[p.first][p.second] + 1;
                que.push(P(nx, ny));
                if(str[nx][ny] == 'm') //骑士和m之间建边
                    add_edge(str[x][y] - 'A' + 1, idx[nx][ny] + k, dist[nx][ny], 1);
            }
        }
    }
}
int main()
{
    int t, n, k, m;
    scanf("%d", &t);
    while(t--)
    {
        cnt = 0;
        memset(head, -1, sizeof head);
        scanf("%d%d%d", &n, &k, &m);
        for(int i = 0; i < n; i++)
            scanf(" %s", str[i]);
        for(int i = 0; i < k; i++)
        {
            scanf("%d", &arr[i]);
            add_edge(0, i + 1, 0, arr[i]);
        }
        for(int i = 0; i < m; i++)
            add_edge(k + i + 1, k + m + 1, 0, 1);
        int num = 0;
        for(int i = 0; i < n; i++)
            for(int j = 0; j < n; j++)
                if(str[i][j] == 'm')
                    idx[i][j] = ++num; //给m编号
        for(int i = 0; i < n; i++)
            for(int j = 0; j < n; j++)
                if(str[i][j] >= 'A' && str[i][j] <= 'Z')
                    bfs(i, j, n, k); //搜索骑士到每个m的距离
        printf("Case %d: %d\n", ++cas, cost_flow(0, k + m + 1, m));
    }
    return 0;
}