動态規劃、最小費用流例題 — nyoj_712 探尋寶藏

/************************************************************************************
描述    (http://acm.nyist.net/JudgeOnline/problem.php?pid=712 探 尋 寶 藏)
        傳說HMH大沙漠中有一個M*N迷宮，裡面藏有許多寶物。某天，Dr.Kong找到了迷宮的地圖，
    他發現迷宮内處處有寶物，最珍貴的寶物就藏在右下角，迷宮的進出口在左上角。當然，迷宮
    中的通路不是平坦的，到處都是陷阱。Dr.Kong決定讓他的機器人卡多去探險。但機器人卡多從
    左上角走到右下角時，隻會向下走或者向右走。從右下角往回走到左上角時，隻會向上走或者
    向左走，而且卡多不走回頭路。（即：一個點最多經過一次）。當然卡多順手也拿走沿路的每
    個寶物。Dr.Kong希望他的機器人卡多盡量多地帶出寶物。請你編寫程式，幫助Dr.Kong計算一
    下，卡多最多能帶出多少寶物。
輸入
    第一行： K 表示有多少組測試資料。
    接下來對每組測試資料：
    第1行: M N
    第2~M+1行： Ai1 Ai2 ……AiN (i=1,…..,m)

    【限制條件】
    2≤k≤5 1≤M, N≤50 0≤Aij≤100 (i=1,….,M; j=1,…,N)
    所有資料都是整數。 資料之間有一個空格。
輸出
    對于每組測試資料，輸出一行：機器人卡多攜帶出最多價值的寶物數

樣例輸入
    2
    2 3
    0 10 10
    10 10 80
    3 3
    0 3 9
    2 8 5
    5 7 100

樣例輸出
    120
    134
**************************************************************************************/

/*************************************************************************************
方法一：DP
雙線dp - 即同時考慮兩條不相交的線，使其線上的和最大
顯然我們需要記錄每一步時兩個線同時往前走的位置(這樣可以容易的控制其不相交).
狀态：dp[k,(x1,y1),(x2,y2)] 在第k步，雙線裡一線在(x1,y1) 二線在(x2,y2) 的最大和
轉移：dp[k,(x1,y1),(x2,y2)] = max(dp[k-1,(x1-1,y1),(x2-1,y2)],
                                  dp[k-1,(x1,y1-1),(x2-1,y2)],
                                  dp[k-1,(x1-1,y1),(x2,y2-1)],
                                  dp[k-1,(x1,y1-1),(x2,y2-1)]) + A[x1][y1] + A[x2][y2];
***************************************************************************************/
#include <cstdio>
#include <algorithm>

using namespace std;

int dp[110][55][55], A[55][55];

int K, M, N;
bool ok(int s, int x1, int x2) {
    if (x1 == x2) return false;
    if (s-x1 < 1 || s-x1 > N || s-x2 < 1 || s-x2 > N)
        return false;
    return true;
}

int main() {    
    scanf("%d", &K);
    while (K--) {
        scanf("%d%d", &M, &N);
        for (int i = 1; i <= M; ++i)
            for (int j = 1; j <= N; ++j)
                scanf("%d", &A[i][j]);
        int S = M+N;
        dp[2][1][1] = A[1][1];
        for (int s = 3; s <= S; ++s)
            for (int x1 = 1; x1 <= M; ++x1)
                for (int x2 = 1; x2 <= M; ++x2) {
                    if (!ok(s, x1, x2)) continue;                    
                    int _max = max(dp[s-1][x1-1][x2-1], dp[s-1][x1-1][x2]);
                    int _max2 = max(dp[s-1][x1][x2-1], dp[s-1][x1][x2]);
                    dp[s][x1][x2] = max(_max, _max2)+A[x1][s-x1]+A[x2][s-x2];
                }
        int ret = max(dp[S-1][M-1][M], dp[S-1][M][M-1])+A[M][N];
        printf("%d\n", ret);
    }

    return 0;
}

//方法二：最小費用流
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>

using namespace std;

const int INF = 0x3f3f3f3f;
const int maxv = 6000;
const int maxe = 20010;

int src, dest, nnode, nedge;
int point[maxe], capa[maxe], cost[maxe], next[maxe];
int head[maxv], q[maxv], d[maxv], p[maxv], num[maxv];
bool inq[maxv];

void init(int n, int s, int t) {
	nnode = n;
	nedge = 0;
	src = s;
	dest = t;
	memset(head, -1, nnode*sizeof(head[0]));
}

void addEdge(int u, int v, int c, int w) {
	point[nedge] = v; capa[nedge] = c; cost[nedge] = w;
	next[nedge] = head[u]; head[u] = nedge++;
	point[nedge] = u; capa[nedge] = 0; cost[nedge] = -w;
	next[nedge] = head[v]; head[v] = nedge++;
}

bool spfa(void) {		
	int front = 0, rear = 1;
	memset(inq, false, sizeof(inq));
	memset(d, 0x3f, sizeof(d)); d[src] = 0;
	q[front] = src; inq[src] = true; p[src] = -1;
	while (front != rear) {
		int u = q[front++];
		inq[u] = false;
		for (int i = head[u]; i != -1; i = next[i]) {
			int v = point[i];
			if (capa[i] > 0 && d[v] > d[u]+cost[i]) {
				d[v] = d[u] + cost[i];
				p[v] = i;
				if (!inq[v]) {
					if (front > 0 && d[v] <= q[front])
						q[--front] = v;
					else q[rear++] = v;
					inq[v] = true;
				}
			}
		}
	}
	return d[dest] != INF;
}

void solve() {
    int ret = 0, delta = INF;
    spfa();
    for (int i = p[dest]; i != -1 ; i = p[point[i^1]])
        delta = min(capa[i], delta);
    for (int i = p[dest]; i != -1 ; i = p[point[i^1]]) {
        capa[i] -= delta;
        capa[i^1] += delta;
    }
    ret += d[dest];

    spfa();
    ret += d[dest];
    printf("%d\n", -ret);
}

int A[110][110];
int main() {
    int K, M, N;
    scanf("%d\n", &K);
    while (K--) {
        scanf("%d%d", &M, &N);
        init(M*N*2, 0, M*N*2-1);
        for (int i = 0; i < M; ++i)
            for (int j = 0; j < N; ++j) scanf("%d", &A[i][j]);
        for (int i = 0; i < M; ++i)
            for (int j = 0; j < N; ++j) {
                addEdge(i*N+j, i*N+j+M*N, 1, -A[i][j]);
                if (i+1 < M) addEdge(i*N+j+M*N, (i+1)*N+j, 1, 0);
                if (j+1 < N) addEdge(i*N+j+M*N, i*N+j+1, 1, 0);
            }
        addEdge(src, src+M*N, 1, 0);
        addEdge(dest-M*N, dest, 1, 0);
        solve();
    }
    return 0;
}
           

轉載于:https://www.cnblogs.com/wlqsun/p/nyoj_712.html