網絡流24題16. 數字梯形問題

2019-11-06 06:24:23

字體：大中小

來源：轉載

供稿：網友

數字梯形問題

Description

給定一個由 n 行數字組成的數字梯形如下圖所示。梯形的第一行有 m 個數字。從梯形的頂部的 m 個數字開始，在每個數字處可以沿左下或右下方向移動，形成一條從梯形的頂至底的路徑。規則 1：從梯形的頂至底的 m條路徑互不相交。規則 2：從梯形的頂至底的 m條路徑僅在數字結點處相交。規則 3：從梯形的頂至底的 m條路徑允許在數字結點相交或邊相交。這里寫圖片描述對于給定的數字梯形，分別按照規則 1，規則 2，和規則 3 計算出從梯形的頂至底的 m 條路徑，使這 m條路徑經過的數字總和最大。

Input

第 1 行中有 2 個正整數 m和 n（m,n<=20），分別表示數字梯形的第一行有 m 個數字，共有 n 行。接下來的 n 行是數字梯形中各行的數字。第 1 行有 m個數字，第 2 行有 m+1 個數字，…。

Output

輸出按照規則 1，規則 2，和規則 3 計算出的最大數字總和。每行一個最大總和。

Sample Input

2 5 2 3 3 4 5 9 10 9 1 1 1 10 1 1 1 1 10 12 1 1

Sample Output

66 75 77

題解

規則(1) 把梯形中每個位置抽象為兩個點<i.a> $<i.a>$ ,<i.b> $<i.b>$ ，建立附加源S匯T。 1、對于每個點i從<i.a> $<i.a>$ 到<i.b> $<i.b>$ 連接一條容量為1，費用為點i權值的有向邊。 2、從S向梯形頂層每個<i.a> $<i.a>$ 連一條容量為1，費用為0的有向邊。 3、從梯形底層每個<i.b> $<i.b>$ 向T連一條容量為1，費用為0的有向邊。 4、對于每個點i和下面的兩個點j，分別連一條從<i.b> $<i.b>$ 到<j.a> $<j.a>$ 容量為1，費用為0的有向邊。求最大費用最大流，費用流值就是結果。

規則(2) 把梯形中每個位置看做一個點i，建立附加源S匯T。 1、從S向梯形頂層每個i連一條容量為1，費用為0的有向邊。 2、從梯形底層每個i向T連一條容量為無窮大，費用為0的有向邊。 3、對于每個點i和下面的兩個點j，分別連一條從i到j容量為1，費用為點i權值的有向邊。求最大費用最大流，費用流值就是結果。

規則(3) 把梯形中每個位置看做一個點i，建立附加源S匯T。 1、從S向梯形頂層每個i連一條容量為1，費用為0的有向邊。 2、從梯形底層每個i向T連一條容量為無窮大，費用為0的有向邊。 3、對于每個點i和下面的兩個點j，分別連一條從i到j容量為無窮大，費用為點i權值的有向邊。求最大費用最大流，費用流值就是結果。

#include<cstdio>#include<iostream>#include<cstring>#include<algorithm>using namespace std;const int N = 1000 * 2 + 10, M = 1000000 + 10, inf = 0x3f3f3f3f;struct Edge{ int fr, to, cap, flow, cost;}edg[M];int hd[N], nxt[M], tot;int s, t;int q[N], inq[N], d[N], p[N], a[N];int n, m, mp[50][50];void insert(int u, int v, int w, int x){ edg[tot].fr = u, edg[tot].to = v, edg[tot].cap = w, edg[tot].flow = 0, edg[tot].cost = x; nxt[tot] = hd[u]; hd[u] = tot; tot++; edg[tot].fr = v, edg[tot].to = u, edg[tot].cap = 0, edg[tot].flow = 0, edg[tot].cost = -x; nxt[tot] = hd[v]; hd[v] = tot; tot++;}bool spfa(int &fl, int &cst){ for(int i = s; i <= t; i++) d[i] = -inf; int head = 0, tail = 1; q[0] = s; inq[s] = 1; d[s] = 0; p[s] = 0; a[s] = inf; while(head != tail){ int u = q[head++]; if(head == 2001) head = 0; inq[u] = 0; for(int i = hd[u]; i >= 0; i = nxt[i]){ Edge &e = edg[i]; if(e.cap > e.flow && d[e.to] < d[u] + e.cost){ d[e.to] = d[u] + e.cost; p[e.to] = i; a[e.to] = min(a[u], e.cap - e.flow); if(!inq[e.to]){ q[tail++] = e.to; if(tail == 2001) tail = 0; inq[e.to] = 1; } } } } if(d[t] == -inf) return false; fl += a[t]; cst += a[t] * d[t]; int u = t; while(u != s){ edg[p[u]].flow += a[t]; edg[p[u]^1].flow -= a[t]; u = edg[p[u]].fr; } return true;}int maxflow(){ int flow = 0, cost = 0; while(spfa(flow, cost)); return cost;}void init(){ scanf("%d%d", &m, &n); for(int i = 1; i <= n; i++) for(int j = 1; j <= m + i - 1; j++) scanf("%d", &mp[i][j]);}int get(int i, int j){ return (m + m + i - 2) * (i - 1) / 2 + j;}void work1(){ int num = get(n, n + m - 1); s = 0, t = num * 2 + 1; memset(hd, -1, sizeof(hd)); for(int i = 1; i <= n; i++) for(int j = 1; j <= m + i - 1; j++){ insert(get(i, j), num + get(i, j), 1, mp[i][j]); if(i < n){ insert(num + get(i, j), get(i+1, j), 1, 0); insert(num + get(i, j), get(i+1, j+1), 1, 0); } } for(int i = 1; i <= m; i++) insert(s, i, 1, 0); for(int i = 1; i <= n + m -1; i++) insert(num + get(n, i), t, 1, 0);