[料金フロー]POJ 2195 Going Home

タイトルリンク:http://poj.org/problem?id=2195
地図には同じ数の人と家があり、すべての人を異なる家に帰らせ、総道のりは最小で、道のりはハミルトニアン距離と定義されています.
昨日から費用の流れを見てみましたが、思想と最大の流れの差は多くありません.ただ、拡張路を探すときに最小の費用の経路を探して拡張します.
最もよく理解されたEKアルゴリズムでは,EKにおけるBFSプロセスは拡張路を探しているが,このプロセスを最も費用のかかる拡張路を探すことに変えればよい.
拡張路の理解については,EKのBFSから見ると,アルゴリズムの過程で,残留ネットワークソース点から集積点までの経路があり,この経路が拡張路である.
それだけに、最小限の費用を増やして道を広げる方法があります.BFSアルゴリズムでは経路があるかどうかしか決定できないので,BFSの代わりに最短回路アルゴリズムを用いる必要があり,経路がなければ距離はINFであり,経路があればアルゴリズムは必ず最短経路であることを保証する.
注意最短アルゴリズムは必ず負のエッジを処理することができます.エッジを取り外すときに負の費用が発生するため、通常SPFAを選択します.
正確性は以上の通りです.拡張アルゴリズムでなければ、どのように費用の流れを書くかはまだ分かりませんが、まだ勉強しなければならないことがたくさんあります.
この問題にとって、最適マッチングで作ることができます.最大ストリームは最大マッチングを行い、費用フローは最適マッチングを行うことができます.難しいのはアルゴリズムではなく、依然として図を作るのが難しい.
コードを貼る.

#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<iostream>
#include<algorithm>
#define pb push_back
#define pii pair<int,int>
#define LL long long int
#define INF 0x7fffffff
#define LLINF 0x7fffffffffffffff
using namespace std;
const int M = 10005;
char maz[105][105];
struct eg{
    int u, v, cap, cost;
    eg(){}
    eg(int a, int b, int c, int d){ u = a, v = b, cap = c, cost = d; };
}edg[M<<2];
int fir[M<<2], nex[M<<2];
int n, m, s, t, ecnt;

void add(int a, int b, int c, int d){
    edg[ecnt] = eg(a, b, c, d);
    nex[ecnt] = fir[a], fir[a] = ecnt++;
    edg[ecnt] = eg(b, a, 0, -d);
    nex[ecnt] = fir[b], fir[b] = ecnt++;
}

int pre[M], dis[M];
int spfa(int s, int t, int n){ //spfa        
    queue<int>q;
    bool vis[M]={0};
    memset(pre, -1, sizeof(pre));
    for(int i = 0; i <= t; ++i) dis[i] = INF;
    dis[s] = 0; vis[s] = 1;
    q.push(s);
    while( !q.empty() ){
        int u = q.front(); q.pop(); vis[u] = 0;
        for(int k = fir[u]; k != -1; k = nex[k]){
            int v = edg[k].v;
            if( edg[k].cap && dis[u] + edg[k].cost < dis[v]){
                dis[v] = edg[k].cost + dis[u];
                pre[v] = k;
                if(!vis[v]){
                    q.push(v);
                    vis[v] = 1;
                }
            }
        }
    }
    return dis[t] != INF;
}
int mincostEK(int s, int t, int n){
    int res = 0, minflow;
    while( spfa(s, t, n)){
        minflow = INF;
        for(int k = pre[t]; k != -1; k = pre[edg[k].u]){
            minflow = min(minflow, edg[k].cap); //             
        }
        for(int k = pre[t]; k != -1; k = pre[edg[k].u]){
            edg[k].cap -= minflow;
            edg[k^1].cap += minflow; //                        +2，   ^1    ，      ，          
        }
        res += dis[t] * minflow; //          ，1    1   
    }
    return res;
}

int as(int x){return  x<0 ? -x : x; } //    OJ       ，          。
int hamt(pii a, pii b){ //       。
    return as( a.first - b.first ) + as( a.second - b.second );
}

vector<pii >per, ho; //              
int main(){
    while(scanf("%d %d%*c", &n, &m) != EOF && (n||m) ){
        memset(fir, -1, sizeof(fir));
        per.clear(); ho.clear();
        s = 0, t = n*m +1, ecnt = 0;
        for(int i = 1; i <= n; ++i) gets(maz[i]+1);

        for(int i = 1; i <= n; ++i) //   i 1  
        for(int j = 1; j <= m; ++j){
            if(maz[i][j] == 'H') {
                add( (i-1)*m+j, t, 1, 0); //       ，  1，  0
                ho.pb( make_pair(i, j) );
            }
            if(maz[i][j] == 'm') {
                add(s, (i-1)*m +j , 1, 0); //      ，  1，  0
                per.pb( make_pair(i,j) );
            }
        }

        for(int i = 0; i <per.size(); ++i){
            for(int j = 0; j < ho.size(); ++j){ //      ，  1，        
                add( (per[i].first-1)*m + per[i].second, (ho[j].first-1)*m +ho[j].second, 1, hamt(per[i], ho[j]));
            }
        }

        printf("%d
",mincostEK(s, t, n*m+2) );
    }
}