PKU 2195 Going Home - kusano

割り当て問題。最小費用流で解ける。
#include <iostream>
#include <string>
#include <vector>

using namespace std;

//  最小費用流　O(fn^2)
//  F: 容量, C: 費用, s: 始点, t: 終点, f: 目標流量
//  返値: 最小コスト、目標流量を流せないなら-1
//  両方向のフローには未対応
//  特定の条件でしか確認していないのでバグがあるかも
int min_cost_flow(vector<vector<int> >F,vector<vector<int> >C,int s,int t,int f)
{
    int INF=1000000000;
    int n=(int)F.size();
    for(int i=0;i<n;i++)for(int j=0;j<n;j++)
        if(F[i][j]>0)C[j][i]=-C[i][j];
    int cost=0;
    vector<int>h(n);
    while(f>0){
        vector<int>dist(n,INF);
        vector<bool>fix(n);
        vector<int>prev(n);
        dist[s]=0;
        while(true){
            int v=-1;
            for(int i=0;i<n;i++)
                if(!fix[i]&&(v==-1||dist[i]<dist[v]))
                    v=i;
            if(v==-1)break;
            for(int i=0;i<n;i++){
                int d=dist[v]+C[v][i]+h[v]-h[i];
                if(F[v][i]>0&&dist[i]>d)dist[i]=d,prev[i]=v;}
            fix[v]=true;}
        if(dist[t]==INF)return-1;
        for(int i=0;i<n;i++)h[i]+=dist[i];
        int d=f;
        for(int i=t;i!=s;i=prev[i])
            d=min(d,F[prev[i]][i]);
        f-=d,cost+=d*h[t];
        for(int i=t;i!=s;i=prev[i])
            F[prev[i]][i]-=d,F[i][prev[i]]+=d;}
    return cost;
}

int main()
{
    while ( true )
    {
        int N,M; cin>>N>>M;
        if ( N==0 && M==0 )
            break;
        vector<string> map(N);
        for ( int i=0; i<N; i++ )
            cin>>map[i];

        vector<int> mx, my, Hx, Hy;
        for ( int y=0; y<N; y++ )
        for ( int x=0; x<M; x++ )
        {
            if ( map[y][x]=='m' )
                mx.push_back(x),
                my.push_back(y);
            if ( map[y][x]=='H' )
                Hx.push_back(x),
                Hy.push_back(y);
        }
        int n = (int)mx.size();

        //  0:        始点
        //  1   - n:  小人
        //  n+1 - 2n: 家
        //  2n+1:     終点
        vector<vector<int> > F(n*2+2,vector<int>(n*2+2));
        vector<vector<int> > C(n*2+2,vector<int>(n*2+2));

        for ( int i=0; i<n; i++ )
            F[0][i+1] = 1;
        for ( int i=0; i<n; i++ )
        for ( int j=0; j<n; j++ )
            F[i+1][n+j+1] = 1,
            C[i+1][n+j+1] = abs(mx[i]-Hx[j])+abs(my[i]-Hy[j]);
        for ( int i=0; i<n; i++ )
            F[n+i+1][2*n+1] = 1;

        cout << min_cost_flow(F,C,0,2*n+1,n) << endl;
    }
}