wing是什么_最短路径floyd算法例题

大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新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;
}