社区讨论

关于TSP问题

xxiezheyuan
学术版参与者 4已保存回复 10

讨论操作

快速查看讨论及其快照的属性，并进行相关操作。

当前回复
10 条
当前快照
1 份
快照标识符
@lotq4qb9
此快照首次捕获于
2023/11/11 15:27
2 年前
此快照最后确认于
2023/11/11 16:59
2 年前
查看原帖
突然在想旅行商问题可不可以这样做：
令 (x,y,z,t,k)(x,y,z,t,k) 表示对于边 (x,y)(x,y)，流量上下界为 [z,t][z,t]，费用为 kk。
  • 对于原图上的点 ii，建立 ui,viu_i,v_i 两个点，连边 (ui,vi,1,1,0)(u_i,v_i,1,1,0)。表示 ii 必须经过恰好一次。
  • 对于原图上的边 (i,j,k)(i,j,k)，连边 (vi,uj,0,1,k)(v_i,u_j,0,1,k)。
  • 枚举起点 ss，连边 (S,us,1,1,0),(uv,T,1,1,0)(S,u_s,1,1,0),(u_v,T,1,1,0)。
然后分别以 S,TS,T 为源点和汇点跑有源汇上下界最小费用可行流即可。
想问一下为什么不对，或者给出 Hack。

回复

共 10 条回复，欢迎继续交流。

正在加载回复...