题目描述:
给定一个由 n 行数字组成的数字梯形如下图所示。
梯形的第一行有 m 个数字。从梯形的顶部的 m 个数字开始，在每个数字处可以沿左下或右下方向移动，形成一条从梯形的顶至底的路径。
分别遵守以下规则：
-
从梯形的顶至底的 m 条路径互不相交；
-
从梯形的顶至底的 m条路径仅在数字结点处相交；
3.从梯形的顶至底的 m条路径允许在数字结点相交或边相交。
思路:最大费用最大流,拆点,一个问建一次图,
第一问:要路径不相交,意思就是m条路径的边和节点都不相交,则拆点后两点连容量为1,价值为自身数字num的边,
限制为只选择一次,然后上面点的出点和下边两个点的入点连边,容量也设置为1.边没有价值,设为0,然后s对m个起点
连容量为1,价值为0的边,表示选取m条路径,再把最下层的所有点的出点与汇点连边,容量为1,费用为0;
第二问:数字可以重复选择,路径还是不能重复,那么就把拆点后的两点容量设置为inf,表示可以无线选取,边的容量不变,与汇点
连边容量也设置为inf,因为从一个点流出的流量可能比1大(最后一个点是多条路径的终点)
第三问:边和路径都可以重复选择,就在上题基础上把边的容量也设置为inf就好了,总之源点与m个起始点的容量为1的边不变就行.
第三问也可以用dp做,时间复杂度O(n*m)速度更快
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 600005;
const int inf = 0x3f3f3f3f;
struct edge {
int f, t, nxt;
ll flow, w;
}e[maxn * 2];
int hd[maxn], tot = 1;
void add(int f, int t, ll flow, ll w) {
e[++tot] = { f,t,hd[f],flow ,w };
hd[f] = tot;
e[++tot] = { t,f,hd[t],0,-w };
hd[t] = tot;
}
int s, t;
int dis[maxn], pre[maxn];
ll maxflow, mincost;
ll cyf[maxn];
bool inque[maxn];
int m, n, total;
bool spfa() {
for (int i = 1; i <=total*2+3; i++) {
dis[i] = -inf; inque[i] = 0;
}
dis[s] = 0, inque[s] = 1, cyf[s] = inf;
queue<int>q;
q.push(s);
while (!q.empty()) {
int u = q.front(); q.pop();
inque[u] = 0;
for (int i = hd[u]; i; i = e[i].nxt) {
int v = e[i].t;
if (e[i].flow > 0 && dis[u] + e[i].w > dis[v]) {
pre[v] = i;
cyf[v] = min(cyf[u], e[i].flow);
dis[v] = dis[u] + e[i].w;
if (!inque[v]) {
inque[v] = 1;
q.push(v);
}
}
}
}
return dis[t] != -inf;
}
void mcmf() {
maxflow = mincost = 0;
while (spfa()) {
int x = t; maxflow += cyf[t]; mincost += dis[t] * cyf[t];
while (x != s) {
int i = pre[x];
e[i].flow -= cyf[t];
e[i ^ 1].flow += cyf[t];
x = e[i].f;
}
}
}
int num[25][3000];
int res[25][3000];
int main() {
//freopen("test.txt", "r", stdin);
scanf("%d%d", &m, &n);
total = (2 * m + n - 1) * n / 2;
s = total*2 + 1, t = s + 1;
int nxt , pre;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m + i - 1; j++) {
scanf("%d", &num[i][j]);
}
}
nxt = 0, pre = 0;
for (int i = 1; i <= n; i++) {
nxt += i + m - 1;
for (int j = 1; j <= m + i-1; j++) {
add(pre + j, pre + j + total, 1, num[i][j]);
if (i == n)continue;
add(pre + j+total, nxt + j, 1, 0);
add(pre + j+total, nxt + j + 1, 1, 0);
}
pre = nxt;
}
for (int i = 1; i <= m; i++) {
add(s, i, 1, 0);
}
for (int i = total - (m + n - 1) + 1; i <= total; i++) {
add(i + total, t, 1, 0);
}
mcmf();
printf("%lld\n", mincost);
memset(hd, 0, sizeof(hd)); tot = 1;
nxt = 0, pre = 0;
for (int i = 1; i <= n; i++) {
nxt += i + m - 1;
for (int j = 1; j <= m + i - 1; j++) {
add(pre + j, pre + j + total, inf, num[i][j]);
if (i == n)continue;
add(pre + j + total, nxt + j, 1, 0);
add(pre + j + total, nxt + j + 1, 1, 0);
}
pre = nxt;
}
for (int i = 1; i <= m; i++) {
add(s, i,1, 0);
}
for (int i = total - (m + n - 1) + 1; i <= total; i++) {
add(i + total, t, inf, 0);
}
mcmf();
printf("%lld\n", mincost);
//dp
/*for (int i = n; i>=1 ; i--) {
for (int j = 1; j <= m + i - 1; j++) {
res[i][j] = max(res[i + 1][j], res[i + 1][j + 1]) + num[i][j];
}
}
ll ans = 0;
for (int i = 1; i <= m; i ++) {
ans += res[1][i];
}
printf("%lld\n", ans);*/
memset(hd, 0, sizeof(hd)); tot = 1;
nxt = 0, pre = 0;
for (int i = 1; i <= n; i++) {
nxt += i + m - 1;
for (int j = 1; j <= m + i - 1; j++) {
add(pre + j, pre + j + total, inf, num[i][j]);
if (i == n)continue;
add(pre + j + total, nxt + j, inf, 0);
add(pre + j + total, nxt + j + 1, inf, 0);
}
pre = nxt;
}
for (int i = 1; i <= m; i++) {
add(s, i, 1, 0);
}
for (int i = total - (m + n - 1) + 1; i <= total; i++) {
add(i + total, t, inf, 0);
}
mcmf();
printf("%lld\n", mincost);
return 0;
}