求助一道感觉是网络流的题目 QAQ
  • 板块学术版
  • 楼主Steadywelkin
  • 当前回复8
  • 已保存回复8
  • 发布时间2021/3/6 16:33
  • 上次更新2023/11/5 02:23:47
查看原帖
求助一道感觉是网络流的题目 QAQ
213841
Steadywelkin楼主2021/3/6 16:33

寒假时我自己想到一道题目,本来认为是一道模版题,但到现在还没做出来,故向各位大佬求助。

题目描述

有一个岛屿群,不同的岛屿之间有桥梁连接,由于桥梁有长有短,还有桥自身的限重,桥自身带有两个权值:通过桥所需要的时间权值、桥的限重权值(以下用能同时通过的车队数表示)。

现在有两个车队(我们认为两个车队的属性是完全一致的,即:对于限重为 11 的桥梁都只能通过一个,限重为 22 的桥梁能同时通过),都要从 海岛 AA 前往 海岛 BB ,请问两个车队中较晚到达的那个车队最早到达 海岛 BB 所需要的时间。

图与注意

在下图中默认以一号节点为起点,五号节点为终点。

桥梁的限重边权有且只有 1122 两种,通过时间权为正整数

2021/3/6 16:33
加载中...