SRM 506 Div1 Medium SlimeXGrandSlimeAuto

topcoder

問題概要

街と道のグラフが与えられて、街の訪問順が与えられる。
いくつかの街に車が点在している。
車は一回の移動につかうと（ある目的地までのると）乗り捨てる。
歩く速度、車の速度が与えられる。
すべての街を訪問するのに最短の時間をもとめよ。

解法

最小費用流
ソースから容量1コスト0のエッジを全ての移動を表すに流し、
それぞれの移動を表すノードから車に、車をのって次の目的地に行くコストで容量1でエッジを張る。
歩く動作を表すノードに容量1コストが歩いて移動する場合のコストでエッジを張る。
それぞれの車からコスト0容量1でシンクにエッジを張る。
歩く動作を表すノードから容量無限コスト0のエッジを張る。
これで、流量が訪問数のフローを流したときの最小費用が答えとなる。
車からシンクの容量が1なので、車にたいして一つの移動しかマッチしない。
ソースからそれぞれの移動を表すノードに対して容量1のエッジしか張っていないこと
かつ
容量が移動数なので、すべての移動は必ず行われる。
歩く動作を表すノードからシンクまでのエッジの容量が無限なことから歩いて移動というのがどの
移動に対してもとることができ、それが制限されないことを表す。

ソース

#include<string>
#include<vector>
#include<queue>

#define REP(i,b,n) for(int i=b;i<(int)n;i++)
#define rep(i,n)   REP(i,0,n)

using namespace std;

const int MAX_V = 1000;
const int INF = 1000000000;

class State{
public:
  int cost, pos;
  bool operator<(const State &s)const{
    return cost > s.cost;
  }
};

class Edge{
public:
  int to, cap, cost, rev;
};

int V, h[MAX_V], dist[MAX_V], prevv[MAX_V], preve[MAX_V];
vector<Edge> G[MAX_V];

void addEdge(int from, int to, int cap, int cost){
  G[from].push_back((Edge){to, cap, cost, G[to].size()});
  G[to].push_back((Edge){from, 0, -cost, G[from].size()-1});
}

int min_cost_flow(int s, int t, int f){
  int ret = 0;
  rep(i, V)h[i] = 0;
  while(f>0){
    priority_queue<State> Q;
    rep(i, V)dist[i] = INF;
    dist[s] = 0;
    Q.push((State){0, s});
    while(!Q.empty()){
      State now = Q.top();
      Q.pop();
      int v = now.pos;
      if(dist[v] < now.cost)continue;
      rep(i, G[v].size()){
        Edge e = G[v][i];
        if(e.cap > 0 && dist[e.to] > dist[v] + e.cost + h[v] - h[e.to]){
          dist[e.to] = dist[v] + e.cost + h[v] - h[e.to];
          prevv[e.to] = v;
          preve[e.to] = i;
          Q.push((State){dist[e.to], e.to});
        }
      }
    }
    if(dist[t] == INF)return -1;
    
    rep(v, V)h[v] += dist[v];
    
    int mini = f;
    for(int v = t;v != s; v = prevv[v]){
      mini = min(mini, G[prevv[v]][preve[v]].cap);
    }
    f -= mini;
    ret += mini * h[t];
    for(int v = t; v != s; v= prevv[v]){
      Edge &e = G[prevv[v]][preve[v]];
      e.cap -= mini;
      G[v][e.rev].cap += mini;
    }
  }
  return ret;
}


int convert(char c){
  if(c == '.')return  INF;
  if(isdigit(c))return (c - '0')+1;
  if(c >= 'a' && c <= 'z')return (c - 'a' + 11);
  if(c >= 'A' && c <= 'Z')return (c - 'A' + 37);
  return INF;
}

const int N = 50;

class SlimeXGrandSlimeAuto {
public:
  int travel(vector <int> cars, vector <int> city, vector <string> roads, int walk, int drive) {
    int cost[N][N], n = roads.size();
    rep(i, n){
      rep(j, n){
        cost[i][j] = convert(roads[i][j]);
      }
      cost[i][i] = 0;
    }
    rep(k, n){
      rep(i, n){
        if(cost[i][k] == INF)continue;
        rep(j, n){
          if(cost[k][j] == INF)continue;
          cost[i][j] = min(cost[i][k] + cost[k][j], cost[i][j]);
        }
      }
    }
    rep(i, MAX_V){
      G[i].clear();
    }
    V = 3 + city.size() + cars.size();
    int now = 0;
    rep(i, city.size()){
      addEdge(i, V-3, 1, cost[now][city[i]] * walk);
      rep(j, cars.size()){
        addEdge(i, city.size() + j, 1, cost[now][cars[j]] * walk + cost[cars[j]][city[i]] * drive); 
      }
      now = city[i];
    }
    rep(i, city.size()){
      addEdge(V-2, i, 1, 0);
    }
    rep(i, cars.size()){
      addEdge(city.size() + i, V-1, 1, 0);
    }
    addEdge(V-3, V-1, INF, 0);
    return min_cost_flow(V-2, V-1, city.size());
  }
};