POJ-3422 : Kaka's Matrix Travels

問題概要

N*N(N<50)のボードがあり、各マスには非負の数が書かれている。左上から右下へK本最短路を選び、通ったマスに書かれた数の和を最大化する問題。

解法

各点の頂点に流量1,コスト-X[i][j]と流量INF,コスト0の制限を付けて自然に有向グラフをつくり、左上から右下へ流量Kの最小費用流を求めればよい。辺の使用量が一定なので負のコストも簡単に解消できる。

acceptされたコード

#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

const int INF = (int)(1.05e9); 

const int MAX_W = 50;

int W, K;
int board[MAX_W][MAX_W];
Graph G;

inline int toIndex(int y, int x) {
	return y*W + x;
}

void init() {
	scanf("%d%d", &W, &K);
	for (int i = 0; i < W; ++i) {
		for (int j = 0; j < W; ++j) {
			scanf("%d", board[i] + j);
		}
	}
}

int solve() {
	G.init(2*W*W);
	for (int y = 0; y < W; ++y) {
		for (int x = 0; x < W; ++x) {
			int index = toIndex(y, x);
			G.addDirectedEdge(2*index+0, 2*index+1, K, 0);
			G.addDirectedEdge(2*index+0, 2*index+1, 1, -board[y][x]);
			if (y < W - 1) {
				int down = toIndex(y+1, x);
				G.addDirectedEdge(2*index + 1, 2*down + 0, K, 0);
			}
			if (x < W - 1) {
				int r = toIndex(y, x+1);
				G.addDirectedEdge(2*index + 1, 2*r + 0, K, 0);
			}
		}
	}
	calcMinCostFlowWithFixedEdge(G, 0, G.numV-1, K, K*((2*W-1) + (2*W-2)));
	return -G.totalCost;
}

int main() {
	init();
	printf("%d\n", solve());
	return 0;
}