大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。
Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺
给定一个由 n 行数字组成的数字梯形如下图所示。
梯形的第一行有 m 个数字。
从梯形的顶部的 m 个数字开始,在每个数字处可以沿左下或右下方向移动,形成一条从梯形的顶至底的路径。
规则 1:从梯形的顶至底的 m 条路径互不相交。
规则 2:从梯形的顶至底的 m 条路径仅在数字结点处相交。
规则 3:从梯形的顶至底的 m 条路径允许在数字结点相交或边相交。
对于给定的数字梯形,分别按照规则 1,规则 2,和规则 3 计算出从梯形的顶至底的 m 条路径,使这 m 条路径经过的数字总和最大。
输入格式
第 1 行中有 2 个正整数 m 和 n,分别表示数字梯形的第一行有 m 个数字,共有 n 行。
接下来的 n 行是数字梯形中各行的数字。第 1 行有 m 个数字,第 2 行有 m+1 个数字,以此类推。
输出格式
将按照规则 1,规则 2,和规则 3 计算出的最大数字总和输出,每行输出一个最大总和。
数据范围
1≤n,m≤20,
梯形中的数字范围 [1,1000]。
输入样例:
2 5
2 3
3 4 5
9 10 9 1
1 1 10 1 1
1 1 10 12 1 1
输出样例:
66
75
77
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1200, M = 4000, INF = 1e8;
int m, n, S, T;
int h[N], e[M], f[M], w[M], ne[M], idx;
int q[N], d[N], pre[N], incf[N];
bool st[N];
int id[40][40], cost[40][40];
void add(int a, int b, int c, int d)
{
e[idx] = b, f[idx] = c, w[idx] = d, ne[idx] = h[a], h[a] = idx ++ ;
e[idx] = a, f[idx] = 0, w[idx] = -d, ne[idx] = h[b], h[b] = idx ++ ;
}
bool spfa()
{
int hh = 0, tt = 1;
memset(d, -0x3f, sizeof d);
memset(incf, 0, sizeof incf);
q[0] = S, d[S] = 0, incf[S] = INF;
while (hh != tt)
{
int t = q[hh ++ ];
if (hh == N) hh = 0;
st[t] = false;
for (int i = h[t]; ~i; i = ne[i])
{
int ver = e[i];
if (f[i] && d[ver] < d[t] + w[i])
{
d[ver] = d[t] + w[i];
pre[ver] = i;
incf[ver] = min(f[i], incf[t]);
if (!st[ver])
{
q[tt ++ ] = ver;
if (tt == N) tt = 0;
st[ver] = true;
}
}
}
}
return incf[T] > 0;
}
int EK()
{
int cost = 0;
while (spfa())
{
int t = incf[T];
cost += t * d[T];
for (int i = T; i != S; i = e[pre[i] ^ 1])
{
f[pre[i]] -= t;
f[pre[i] ^ 1] += t;
}
}
return cost;
}
int main()
{
int cnt = 0;
scanf("%d%d", &m, &n);
S = ++ cnt;
T = ++ cnt;
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= m + i - 1; j ++ )
{
scanf("%d", &cost[i][j]);
id[i][j] = ++ cnt;
}
// 规则1
memset(h, -1, sizeof h), idx = 0;
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= m + i - 1; j ++ )
{
add(id[i][j] * 2, id[i][j] * 2 + 1, 1, cost[i][j]);
if (i == 1) add(S, id[i][j] * 2, 1, 0);
if (i == n) add(id[i][j] * 2 + 1, T, 1, 0);
if (i < n)
{
add(id[i][j] * 2 + 1, id[i + 1][j] * 2, 1, 0);
add(id[i][j] * 2 + 1, id[i + 1][j + 1] * 2, 1, 0);
}
}
printf("%d\n", EK());
// 规则2
memset(h, -1, sizeof h), idx = 0;
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= m + i - 1; j ++ )
{
add(id[i][j] * 2, id[i][j] * 2 + 1, INF, cost[i][j]);
if (i == 1) add(S, id[i][j] * 2, 1, 0);
if (i == n) add(id[i][j] * 2 + 1, T, INF, 0);
if (i < n)
{
add(id[i][j] * 2 + 1, id[i + 1][j] * 2, 1, 0);
add(id[i][j] * 2 + 1, id[i + 1][j + 1] * 2, 1, 0);
}
}
printf("%d\n", EK());
// 规则3
memset(h, -1, sizeof h), idx = 0;
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= m + i - 1; j ++ )
{
add(id[i][j] * 2, id[i][j] * 2 + 1, INF, cost[i][j]);
if (i == 1) add(S, id[i][j] * 2, 1, 0);
if (i == n) add(id[i][j] * 2 + 1, T, INF, 0);
if (i < n)
{
add(id[i][j] * 2 + 1, id[i + 1][j] * 2, INF, 0);
add(id[i][j] * 2 + 1, id[i + 1][j + 1] * 2, INF, 0);
}
}
printf("%d\n", EK());
return 0;
}
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/169074.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...