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; }