SRM506 Div1 Medium(600) SlimeXGrandSlimeAuto

SlimeXGrandSlimeAuto

それぞれの車をどの移動に使うかという割り当て問題。最小費用流で解ける。

#include <string>
#include <vector>
using namespace std;

//  全点対間最短路（Warshall-Floyd法）
vector<vector<int> >warshall_floyd(vector<vector<int> >E)
{
    int n=(int)E.size();
    for(int i=0;i<n;i++)for(int j=0;j<n;j++)for(int k=0;k<n;k++)
        E[j][k]=min(E[j][k],E[j][i]+E[i][k]);
    return E;
}

//  最小費用流　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;
}

class SlimeXGrandSlimeAuto{public:
int travel( vector <int> cars, vector <int> districts, vector <string> roads, int inverseWalkSpeed, int inverseDriveSpeed )
{
    //  全点対間距離
    int N = (int)roads.size();

    vector<vector<int> > dist(N,vector<int>(N,10000));

    for ( int i=0; i<N; i++ )
    for ( int j=0; j<N; j++ )
    {
        char c = roads[i][j];
        if ( '0'<=c && c<='9' )  dist[i][j] = c-'0'+ 1;
        if ( 'a'<=c && c<='z' )  dist[i][j] = c-'a'+11;
        if ( 'A'<=c && c<='Z' )  dist[i][j] = c-'A'+37;
    }
    for ( int i=0; i<N; i++ )
        dist[i][i] = 0;

    dist = warshall_floyd(dist);

    int n = (int)districts.size();
    int m = (int)cars.size();

    districts.insert(districts.begin(),0);

    //  0:         始点
    //  1   - n:   目的地への移動
    //  n+1 - n+m: 車
    //  n+m+1:     終点
    vector<vector<int> > F(n+m+2,vector<int>(n+m+2));
    vector<vector<int> > C(n+m+2,vector<int>(n+m+2));

    for ( int i=0; i<n; i++ )
    {
        F[0][i+1] = 1;
        //  車を使う
        for ( int j=0; j<m; j++ )
            F[i+1][n+j+1] = 1,
            C[i+1][n+j+1] = dist[districts[i]][cars[j]] * inverseWalkSpeed
                          + dist[cars[j]][districts[i+1]] * inverseDriveSpeed;
        //  車を使わない
        F[i+1][n+m+1] = 1;
        C[i+1][n+m+1] = dist[districts[i]][districts[i+1]] * inverseWalkSpeed;
    }
    for ( int i=0; i<m; i++ )
        F[n+i+1][n+m+1] = 1;

    return min_cost_flow(F,C,0,n+m+1,n);
}};