POJ 3422 Kaka's Matrix Travels

問題

NxNのグリッドがあり、各マスに0以上の整数が書かれている。グリッドの左上のマスからスタートして右か下に一つずつ移動して右下のマスまでたどり着きたい。通ったマスの数字は得点となり、一度通ったらそのマスの数字は0になる。K回スタートからゴールに移動したときに得られる総得点を最大化せよ。

やりかた

最小（最大）費用流。単純に最大経路をK回調べるのでは駄目。
費用流の問題として考えるとソースから左上のマスにつながり、右下のマスからシンクにつながるネットワークにKだけ流すときの最大費用流として考えることができる。ここで問題になるのは各マスが一回通ったあとは得点が0になることであり、ネットワークフローで考えればこれは（得点があるときの）そのセルに流量1の制限があることと同じになる。そこで下の図のように各マスのコピーを作り、コピーに対して1の流量のある得点がつく辺と、流量無限大のコスト0の辺を加えてやることで、得点のある辺は一回しか使われないようにすることができる。

以下ソース。

int N, K;
struct min_cost_flow{
  struct edge{
    int to, cap, cost, rev;
    edge(int to, int cap, int cost, int rev) : 
      to(to), cap(cap), cost(cost), rev(rev) {};
  };
  vector<vector<edge> > G;

  min_cost_flow(int V) : G(V) {}

  void add_edge(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 flow(int s, int t, int f){
    typedef pair<int, int> P;
    int V = G.size();
    vector<int> po(V);
    int res = 0;
    while(f > 0){
      vector<int> dist(V, INF), prevv(V, -1), preve(V, -1);
      priority_queue<P, vector<P>, greater<P> > Q;
      Q.push(make_pair(0, s));
      dist[s] = 0;
      while(!Q.empty()){
	P q = Q.top(); Q.pop();
	int u = q.second;
	if(dist[u] < q.first) continue;
	for(int i = 0; i < G[u].size(); i++){
	  edge &e = G[u][i];
	  if(e.cap > 0 && dist[e.to] > dist[u] + e.cost + po[u] - po[e.to]){
	    dist[e.to] = dist[u] + e.cost + po[u] - po[e.to];
	    prevv[e.to] = u;   preve[e.to] = i;
	    Q.push(P(dist[e.to], e.to));
	  }
	}
      }
      if(dist[t] == INF) return -1;
      for(int v = 0; v < V; v++) po[v] += dist[v];
      
      int scap = f;
      for(int v = t; v != s; v = prevv[v])
	scap = min(scap, G[prevv[v]][preve[v]].cap);
      
      f -= scap;
      res += scap * po[t];
      for(int v = t; v != s; v = prevv[v]){
	edge &e = G[prevv[v]][preve[v]];
	e.cap -= scap;
	G[v][e.rev].cap += scap;
      }
    }
    return res;
  }
};

int main(){
  scanf("%d %d", &N, &K);

  int V = N * N;
  int s = 2 * V, t = s + 1;
  
  min_cost_flow mcf(2 * V + 2);
  for(int i = 0; i < N; i++){
    for(int j = 0; j < N; j++){
      int x;
      scanf("%d", &x);

      mcf.add_edge(i * N + j, i * N + j + V, 1, -x);//最小費用流でとくため符号を反転
      mcf.add_edge(i * N + j, i * N + j + V, INF, 0);
      
      if(j != N - 1)
	mcf.add_edge(i * N + j + V, i * N + j + 1, INF, 0);
      if(i != N - 1)
      	mcf.add_edge(i * N + j + V, (i + 1) * N + j, INF, 0);
    }
  }
  mcf.add_edge(s, 0, INF, 0);
  mcf.add_edge(2 * V - 1, t, INF, 0);
  
  printf("%d\n", -mcf.flow(s, t, K));////最小費用流でとくため符号を反転
  return 0;
}

図が薄くてすみません。