一道图论题

学术版

Otomachi_Una_ @ 2021-12-14 21:59:44

一个 n 阶 m 边带权连通图。求一条可重复边路径，经过所有点。求该路径边权值之和最小值（重复边重复算）。

n\leq2\times 10^3

by BlankAo @ 2021-12-14 22:04:42

如果有从起点开始可以到达的负环，答案就是-inf，否则路径不会重复

by Otomachi_Una_ @ 2021-12-14 22:07:55

@BlankAo 边会重复，比如

u v w
1 2 1
2 3 1
3 4 1
3 5 1
5 6 1

by Otomachi_Una_ @ 2021-12-14 22:36:32

@MicroMaker 迹是树是对的，但不一定是最小生成树罢

by MyukiyoMekya @ 2021-12-14 22:40:42

@ushg8877 所以说就是要求一个生成树，使得边权和两倍减去直径最小？

by Otomachi_Una_ @ 2021-12-14 22:41:24

@MicroMaker 是的吧

by QwQcOrZ @ 2021-12-14 22:46:12

1 3 100
2 3 100
3 4 1
4 5 1
5 6 1
3 6 2

Hacked

by QwQcOrZ @ 2021-12-14 22:46:30

@ushg8877

by yzhang @ 2021-12-15 16:34:34

@MicroMaker 显然这个很假吧

by MyukiyoMekya @ 2021-12-15 18:30:11

@yzhang 已经被上面的老哥hack了/qd

|