UTPC 2011 問題 H : キャッシュ戦略

UTPC 2011 問題 H : キャッシュ戦略
http://www.utpc.jp/2011/problems/cache.html

問題概要

日本語でとても簡潔なため略

解法

最小費用流
解説に詳しく、どのようにグラフを作れば解けるか乗っているので参照。
http://www.utpc.jp/2011/
しかし、負の辺があり、かつ、ノードが10000個あり、
エッジが20000個くらいになりそうなので、なかなか難しい。
まず、負の辺を含むためポテンシャルを求めなければならない。
しかし、ベルマンフォードはサイズ的に苦しい。
->簡単なDPで求める。この問題は一直線に並んだノードにシンク方向にエッジが伸びているだけなので、簡単に求まる。
同じ玉が2個続いた場合、普通にエッジを足すと負の閉路になってしまう

• >そのときだけ別処理

ソース

#include<iostream>
#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 INF = 1000000000;
const int N = 10001;
 
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[N], dist[N], prevv[N], preve[N];
vector<Edge> G[N];
 
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;
  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 main(){
  int m, n, k;
  cin >> m >> n >> k;
  int w[N], order[N], sum = 0;
  rep(i, n){
    cin >> w[i];
  }
  rep(i, k){
    cin >> order[i];
    order[i]--;
    if(i > 0 && order[i] == order[i-1]) continue;
    sum += w[order[i]];
  }
  int last[N];
  rep(i, n){
    last[i] = -1;
  }
  V = k;
  int mini = 0;
  rep(i, k){
    if(last[order[i]] != -1){
      if(last[order[i]] + 1 != i)
        addEdge(last[order[i]] + 1, i, 1, -w[order[i]]);
      mini -= w[order[i]];
    }
    last[order[i]] = i;
    if(i != 0) addEdge(i-1, i, INF, 0);
    h[i] = mini;
  }
  cout << sum  + min_cost_flow(0, k-1, m-1) << endl;;
  return 0;
}