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

wing是什么_最短路径floyd算法例题给定一个由 n 行数字组成的数字梯形如下图所示。梯形的第一行有 m 个数字。从梯形的顶部的 m 个数字开始,在每个数字处可以沿左下或右下方向移动,形成一条从梯形的顶至底的路径。规则 1:从梯形的顶至底的 m 条路径互不相交。规则 2:从梯形的顶至底的 m 条路径仅在数字结点处相交。规则 3:从梯形的顶至底的 m 条路径允许在数字结点相交或边相交。对于给定的数字梯形,分别按照规则 1,规则 2,和规则 3 计算出从梯形的顶至底的 m 条路径,使这 m 条路径经过的数字总和最大。输入格式第 1

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

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • java连接MQTT服务器(Springboot整合MQTT)

    java连接MQTT服务器(Springboot整合MQTT)目录一、业务场景二、本文只讲解java连接MQTT服务器进行数据处理一、业务场景硬件采集的数据传入EMQX平台(采用MQTT协议),java通过代码连接MQTT服务器,进行采集数据接收、解析、业务处理、存储入库、数据展示。MQTT是基于发布(Publish)/订阅(Subscribe)模式来进行通信及数据交换的。二、本文只讲解java连接MQTT服务器进行数据处理…

  • flex布局垂直居中

    flex布局垂直居中使用flex布局实现下面图中效果:外框高都为400px,边框为2px;圆的宽高为100px;中圆是水平居中;下圆是水平居中以及相对于中圆垂直居中(下圆到中圆的距离和下圆到下边框的距离相等)。效果如图:我的实现方法是笨办法,大佬们多指点<divclass=”box”><divclass=”item”><divclass=”child”></div></di

  • ideaVim_ij idea

    ideaVim_ij idea原文地址:https://www.cnblogs.com/zhaozihan/p/6297217.htmlIdeaVim简介IdeaVim是IntelliJIDEA的一款插件,他提高了我们写代码的速度,对代码的跳转,查找也很友好。安装位置安装之后它在Tools>VimEmulator具体操作i模式i模式即为编辑模式,按下字母

  • RPC协议及常用框架

    RPC协议及常用框架https://www.jianshu.com/p/8ba4b7b834aaRPC协议RPC:远程过程调用,原则上来说系统间跨进程的调用都属于RPC范畴RMI/HTTP/dubbo/SpringCloud/thriftRPC框架如何实现分布式环境下的远程调用在一个典型的RPC的使用场景中,包含了服务发现,负载,容错,网络传输,序列化等组件,其中RPC协议指明了程序如何进行网络传输和序列化。RPC协议的组成RPC协议的组成1.地址:服务提供者地址2.端口:.

  • webstorm激活码2021【注册码】[通俗易懂]

    webstorm激活码2021【注册码】,https://javaforall.cn/100143.html。详细ieda激活码不妨到全栈程序员必看教程网一起来了解一下吧!

  • win7系统如何在防火墙里开放端口

    win7系统如何在防火墙里开放端口

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号