k****f
发帖数: 3794 | 1 一个图G，有n个节点，有e条边连接节点，每个边有权重 w(i,j)
要求从第一个节点到第n个节点找出k条不同路径
这k条路径除了在头尾（第一和第n个节点）上有相同节点，其他的经过的节点都不相同。
要求k条路径的权重总和最小。
当k＝1的时候，就是经典的dijkstra算法。复杂度就是边数
当k＝2以上的时候，好像就不好解了。 |
e*****w
发帖数: 144 | 2 一共就n个节点，怎么才能让k条路“经过的节点都不相同”？
同。
【在 k****f 的大作中提到】
: 一个图G，有n个节点，有e条边连接节点，每个边有权重 w(i,j)
: 要求从第一个节点到第n个节点找出k条不同路径
: 这k条路径除了在头尾（第一和第n个节点）上有相同节点，其他的经过的节点都不相同。
: 要求k条路径的权重总和最小。
: 当k＝1的时候，就是经典的dijkstra算法。复杂度就是边数
: 当k＝2以上的时候，好像就不好解了。
|
k****f
发帖数: 3794 | 3 有些路径只要很少的几个node就可以连接上的，不需要走遍所有的node
【在 e*****w 的大作中提到】
: 一共就n个节点，怎么才能让k条路“经过的节点都不相同”？
:
: 同。
|
e*****w
发帖数: 144 | 4 i see. 贪心好像不行，貌似有点小难。
【在 k****f 的大作中提到】
: 有些路径只要很少的几个node就可以连接上的，不需要走遍所有的node
|
s****u
发帖数: 118 | 5 网络流
同。
【在 k****f 的大作中提到】
: 一个图G，有n个节点，有e条边连接节点，每个边有权重 w(i,j)
: 要求从第一个节点到第n个节点找出k条不同路径
: 这k条路径除了在头尾（第一和第n个节点）上有相同节点，其他的经过的节点都不相同。
: 要求k条路径的权重总和最小。
: 当k＝1的时候，就是经典的dijkstra算法。复杂度就是边数
: 当k＝2以上的时候，好像就不好解了。
|
k****f
发帖数: 3794 | 6 关键是有两个路径之间不能有公共的点(除了首尾)，
这个约束处理起来比较麻烦的。
【在 s****u 的大作中提到】
: 网络流
:
: 同。
|
s****u
发帖数: 118 | 7 一个点拆两个点，容量1，费用0
很常规的处理方法吧
【在 k****f 的大作中提到】
: 关键是有两个路径之间不能有公共的点(除了首尾)，
: 这个约束处理起来比较麻烦的。
|
k****f
发帖数: 3794 | 8 能不能具体说说么？
有k个flow的
【在 s****u 的大作中提到】
: 一个点拆两个点，容量1，费用0
: 很常规的处理方法吧
|
s****u
发帖数: 118 | 9 每个点V拆成两个点X,Y
除了源跟汇点，X,Y之间连一条边，容量为1，费用为0
如果原图中有边(V,V')，容量C，费用W，新图就(Y,X')连一条边，容量C，费用W
对于源点，(X,Y)这条边容量为k，费用为0；汇点同样
最后求一个从源到汇的最小费用最大流
【在 k****f 的大作中提到】
: 能不能具体说说么？
: 有k个flow的
|
k****f
发帖数: 3794 | 10 多谢了！！
【在 s****u 的大作中提到】
: 每个点V拆成两个点X,Y
: 除了源跟汇点，X,Y之间连一条边，容量为1，费用为0
: 如果原图中有边(V,V')，容量C，费用W，新图就(Y,X')连一条边，容量C，费用W
: 对于源点，(X,Y)这条边容量为k，费用为0；汇点同样
: 最后求一个从源到汇的最小费用最大流
|
s****u
发帖数: 118 | 11 对了，那个C就是1吧，否则大于1不能这样求，因为费用是单位费用 -_-
【在 k****f 的大作中提到】
: 多谢了！！
|
k****f
发帖数: 3794 | 12 呵呵，还在复习network flow算法，
我的问题C刚好是1。
【在 s****u 的大作中提到】
: 对了，那个C就是1吧，否则大于1不能这样求，因为费用是单位费用 -_-
|
k****f
发帖数: 3794 | 13 顺便再问问
如果题目改成：
k个path中最大的权重最小(min max问题)，（原来是要求总和最小, sum）
能不能用同样的技巧呢？
【在 s****u 的大作中提到】
: 对了，那个C就是1吧，否则大于1不能这样求，因为费用是单位费用 -_-
|
s****u
发帖数: 118 | 14 同样做法不行吧 -_-
去想想..
【在 k****f 的大作中提到】
: 顺便再问问
: 如果题目改成：
: k个path中最大的权重最小(min max问题)，（原来是要求总和最小, sum）
: 能不能用同样的技巧呢？
|
