lightoj 1243 - Guardian Knights 最小费用流

#include <cstdio>

#include <cstring>

#include <iostream>

#include <cmath>

#include <algorithm>

#include <queue>

#include <vector>

using namespace std;

const int maxe = ;

const int maxn = ;

const int INF  = 0x3f3f3f3f;

struct Edge{

    int u,v,flow,cap,cost;

    int next;

    Edge(int u=,int v=,int flow=,int cap=,int cost=,int next=):

        u(u), v(v), flow(flow), cap(cap), cost(cost), next(next){}

};

struct MCMF{

    Edge edges[maxe];

    int head[maxn],cnt;

    int d[maxn];

    bool inq[maxn];

    int pa[maxn];

    int res[maxn];

    void init(){

        memset(head,-,sizeof(head));

        cnt = ;

    }

    void addedge(int u,int v,int cap,int cost){

        edges[cnt] = Edge(u,v,,cap,cost,head[u]);

        head[u] = cnt++;

        edges[cnt] = Edge(v,u,,,-cost,head[v]);

        head[v] = cnt++;

    }

    bool SPFA(int s,int t,int& flow,int& cost){

        memset(d,0x3f,sizeof(d));

        memset(inq,,sizeof(inq));

        queue<int> Q;

        Q.push(s);

        inq[s] = true;  d[s] = ;

        res[s] = INF;  res[t] = ;

        while(!Q.empty()){

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

            inq[u] = false;

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

                Edge&  e = edges[i];

                if(e.cap>e.flow && d[e.v] > d[u] + e.cost){

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

                    pa[e.v] = i;

                    res[e.v] = min(res[u],e.cap-e.flow);

                    if(!inq[e.v]){

                        Q.push(e.v);

                        inq[e.v] = true;

                    }

                }

            }

        }

        if(res[t] == )  return false;

        flow += res[t];

        cost += res[t]*d[t];

        for(int i=t;i!=s;i=edges[pa[i]].u){

            edges[pa[i]].flow   += res[t];

            edges[pa[i]^].flow -= res[t];

        }

        return true;

    }

    int MinCost(int s,int t){

        int flow = ,cost = ;

        while(SPFA(s,t,flow,cost)){}

        return cost;

    }

}solver;

struct Node{

    int x,y;

    int dist;

    Node(int x=,int y=,int dist = ): x(x), y(y) ,dist(dist) {}

};

Node Knight[];

int n,k,m;

int dist[][];

int Mymap[][];  // == 0代表rock，-1代表space ,1-m代表mill.

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

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

void bfs(){

    bool vis[][];

    memset(dist,0x3f,sizeof(dist));

    queue<Node> Q;

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

        while(!Q.empty())  Q.pop();

        Q.push(Node(Knight[i].x,Knight[i].y,));

        memset(vis,,sizeof(vis));

        vis[Knight[i].x][Knight[i].y] = true;

        while(!Q.empty()){

            Node out = Q.front(); Q.pop();

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

                int x = out.x + next_x[j];

                int y = out.y + next_y[j];

                if(vis[x][y]) continue;

                vis[x][y] = true;

                if(Mymap[x][y] == -){

                    Q.push(Node(x,y,out.dist+));

                }

                else if(Mymap[x][y]>){

                    dist[i][Mymap[x][y]] = out.dist+;

                    Q.push(Node(x,y,out.dist+));

                }

            }

        }

    }

}

int main()

{

    //freopen("E:\\acm\\input.txt","r",stdin);

    int T;

    cin>>T;

    for(int cas=;cas<=T;cas++){

        cin>>n>>k>>m;

        char ch[];

        memset(Mymap,,sizeof(Mymap));

        int cntm = ;

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

            scanf("%s",ch+);

            for(int j=;j<=n;j++){

               if(ch[j]>='A' && ch[j]<='Z'){

                  int num = ch[j] - 'A' + ;

                  Knight[num] = Node(i,j,);

                  Mymap[i][j] = -;

               }

               else if(ch[j] == 'm'){

                  Mymap[i][j] = cntm++;

               }

               else if(ch[j] == '.'){

                  Mymap[i][j] = -;

               }

            }

        }

        bfs();

        solver.init();

        int s = ,  t = k+m+;

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

            int a;

            scanf("%d",&a);

            solver.addedge(s,i,a,);

        }

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

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

                solver.addedge(i,k+j,,dist[i][j]);

        }

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

            solver.addedge(k+i,t,,);

        }

        printf("Case %d: %d\n",cas,solver.MinCost(s,t));

    }

}