logo
Redian新闻
>未名空间
>Programming - 葵花宝典
>
这个图问题的复杂度是多少呢
avatar
这个图问题的复杂度是多少呢# Programming - 葵花宝典
k*f
1 楼
一个图G，有n个节点，有e条边连接节点，每个边有权重 w(i,j)
要求从第一个节点到第n个节点找出k条不同路径
这k条路径除了在头尾（第一和第n个节点）上有相同节点，其他的经过的节点都不相同。
要求k条路径的权重总和最小。
当k＝1的时候，就是经典的dijkstra算法。复杂度就是边数
当k＝2以上的时候，好像就不好解了。
avatar
e*w
2 楼
一共就n个节点，怎么才能让k条路“经过的节点都不相同”？

同。

【在 k****f 的大作中提到】
: 一个图G，有n个节点，有e条边连接节点，每个边有权重 w(i,j)
: 要求从第一个节点到第n个节点找出k条不同路径
: 这k条路径除了在头尾（第一和第n个节点）上有相同节点，其他的经过的节点都不相同。
: 要求k条路径的权重总和最小。
: 当k＝1的时候，就是经典的dijkstra算法。复杂度就是边数
: 当k＝2以上的时候，好像就不好解了。
avatar
k*f
3 楼
有些路径只要很少的几个node就可以连接上的，不需要走遍所有的node

【在 e*****w 的大作中提到】
: 一共就n个节点，怎么才能让k条路“经过的节点都不相同”？
:
: 同。
avatar
e*w
4 楼
i see. 贪心好像不行，貌似有点小难。

【在 k****f 的大作中提到】
: 有些路径只要很少的几个node就可以连接上的，不需要走遍所有的node
avatar
s*u
5 楼
网络流

同。

【在 k****f 的大作中提到】
: 一个图G，有n个节点，有e条边连接节点，每个边有权重 w(i,j)
: 要求从第一个节点到第n个节点找出k条不同路径
: 这k条路径除了在头尾（第一和第n个节点）上有相同节点，其他的经过的节点都不相同。
: 要求k条路径的权重总和最小。
: 当k＝1的时候，就是经典的dijkstra算法。复杂度就是边数
: 当k＝2以上的时候，好像就不好解了。
avatar
k*f
6 楼
关键是有两个路径之间不能有公共的点(除了首尾)，
这个约束处理起来比较麻烦的。

【在 s****u 的大作中提到】
: 网络流
:
: 同。
avatar
s*u
7 楼
一个点拆两个点，容量1，费用0
很常规的处理方法吧

【在 k****f 的大作中提到】
: 关键是有两个路径之间不能有公共的点(除了首尾)，
: 这个约束处理起来比较麻烦的。
avatar
k*f
8 楼
能不能具体说说么？
有k个flow的

【在 s****u 的大作中提到】
: 一个点拆两个点，容量1，费用0
: 很常规的处理方法吧
avatar
s*u
9 楼
每个点V拆成两个点X,Y
除了源跟汇点，X,Y之间连一条边，容量为1，费用为0
如果原图中有边(V,V')，容量C，费用W，新图就(Y,X')连一条边，容量C，费用W
对于源点，(X,Y)这条边容量为k，费用为0；汇点同样
最后求一个从源到汇的最小费用最大流

【在 k****f 的大作中提到】
: 能不能具体说说么？
: 有k个flow的
avatar
k*f
10 楼
多谢了！！

【在 s****u 的大作中提到】
: 每个点V拆成两个点X,Y
: 除了源跟汇点，X,Y之间连一条边，容量为1，费用为0
: 如果原图中有边(V,V')，容量C，费用W，新图就(Y,X')连一条边，容量C，费用W
: 对于源点，(X,Y)这条边容量为k，费用为0；汇点同样
: 最后求一个从源到汇的最小费用最大流
avatar
s*u
11 楼
对了，那个C就是1吧，否则大于1不能这样求，因为费用是单位费用 -_-

【在 k****f 的大作中提到】
: 多谢了！！
avatar
k*f
12 楼
呵呵，还在复习network flow算法，
我的问题C刚好是1。

【在 s****u 的大作中提到】
: 对了，那个C就是1吧，否则大于1不能这样求，因为费用是单位费用 -_-
avatar
k*f
13 楼
顺便再问问
如果题目改成：
k个path中最大的权重最小(min max问题)，（原来是要求总和最小, sum）
能不能用同样的技巧呢？

【在 s****u 的大作中提到】
: 对了，那个C就是1吧，否则大于1不能这样求，因为费用是单位费用 -_-
avatar
s*u
14 楼
同样做法不行吧 -_-
去想想..

【在 k****f 的大作中提到】
: 顺便再问问
: 如果题目改成：
: k个path中最大的权重最小(min max问题)，（原来是要求总和最小, sum）
: 能不能用同样的技巧呢？
相关阅读
怎样在LINUX下C++程序里延迟1msHow to make a self-signed certificate and use it for NetscaVBA questionhow to reverse a HUGE list?Please Help, dynamic memory after fork()[合集] 为什么不能: declare a static memeber funcMatrix calculation in C++new and delete in c++can struct be derived from?When are data members initialized? what about static data m这个同学很神a question about CGIC++，大家觉得最值得买最想买最不后悔买的书是哪本？standard C++ lib.how to read CPU time in Fortranjava + javascript open local file?What language I should use?sdk那个register directories with vs有什么用？HTML print an image为什么我不能通过proxy访问本地数据库？
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章，不代表同意其说法或描述，仅为提供更多信息，也不构成任何建议。文章信息的合法性及真实性由其作者负责，与Redian.news及其运营公司无关。欢迎投稿，如发现稿件侵权，或作者不愿在本网发表文章，请版权拥有者通知本网处理。