链接

https://loj.ac/p/6010

题意

给定一个由 n 行数字组成的数字梯形如下方所示。梯形的第一行有 m 个数字。从梯形的顶部的 m 个数字开始,在每个数字处可以沿左下或右下方向移动,形成一条从梯形的顶至底的路径。

分别遵守以下规则:

  1. 从梯形的顶至底的 m 条路径互不相交;
  2. 从梯形的顶至底的 m 条路径仅在数字结点处相交;
  3. 从梯形的顶至底的 m 条路径允许在数字结点相交或边相交。

按照规则 1,规则 2,和规则 3 计算出的最大数字总和并输出,每行一个最大总和。

阅读全文 »

链接

https://loj.ac/p/6122

题意

给定一张航空图,图中顶点代表城市,边代表两个城市间的直通航线。现要求找出一条满足下述限制条件的且途经城市最多的旅行路线。

从最西端城市出发,单向从西向东途经若干城市到达最东端城市,然后再单向从东向西飞回起点(可途经若干城市)。

除起点城市外,任何城市只能访问一次。

对于给定的航空图,试设计一个算法找出一条满足要求的最佳航空旅行路线。

阅读全文 »

链接

https://ac.nowcoder.com/acm/contest/9986/H

题意

有一张 n 个点 m 条边的图,每条边连接点 ui,vi,边权为 wi。他想进行 q 次操作,有如下两种类型:

  1. 修改第 x 条边为连接点 y,z,边权为 t
  2. 查询只用编号在 [l,r] 范围内的边,得到的最小生成树权值是多少。

数据范围:

1n200,1m30000,1q30000,1ui,vin,1wi100000

1xm,1y,zn,1t100000

阅读全文 »
0%