社区讨论
求助一个简单的问题!!悬赏RMB!!
学术版参与者 2已保存回复 2
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 2 条
- 当前快照
- 1 份
- 快照标识符
- @lo29qj6l
- 此快照首次捕获于
- 2023/10/23 10:18 2 年前
- 此快照最后确认于
- 2023/11/03 10:30 2 年前
大概是这样的,现在有一张简单无向联通图,我现在想要在上面找出一棵满足某些条件的生成树,我设计了这样的网络流算法。
首先缩个边双,原图变成一棵树,树边必取,现在来考虑边双内部的边
然后把边变成点,编号为 ,原图中的点仍然是点,编号为 。
我们来考虑流量的意义,我认为流量的意义是点的度数。
那么我们对于一个边双的任务相当于是缩成一棵树,所以我们建立一个代表这个边双的点,然后这个边双内部的点全部连向这个边双,流量为无穷大,这个边双流向汇点,流量为缩成树之后所有点的度数和,也就是边双大小与一的差的两倍。
但是这还没完,因为生成树要求每个点都要被连一遍,怎么办呢,对于每个点,都要至少被连接一次,这启发我们加上一层费用,连接一条流量为1,费用为无穷小的边向边双,再连接一条流量为无穷大,费用为0的边向边双,那么为了让费用最小,我们就会至少走一次某个点。
我们对于所有边,考虑连两条流量为 1 ,费用为 0 的边到他这条边本来拉的点上面。
然后因为这棵生成树需要满足一些神奇的限制条件,这个限制条件是作在边上的,比如说某种边的条数,所以我们就把条件作为一个新点,源点连一条流量为【需要满足的限制条件的数量】,费用为 0 的边到限制条件上,限制条件连接到满足限制条件的边上,流量为 2.,费用为0,因为一个点提供两个点的度数。
然后跑一遍费用流,当且仅当限制条件流满(满足限制条件),边双流满(满足边数不多不少),同时每个点的第一次流满(满足每个点都被顾及到),如果都做到了就是满足条件的生成树,而生成树的边的组成部分则是最开始限制条件流向的边中满流的边以及缩完边双后的树边。
乍一看好像很有道理,写完这部分代码之后,经过测试,出现了一个问题,就是有可能一条边两个流量不会流完,因为假设有这样一种情况,就是一条边一边连着一个点的第一次,为了获得无穷小的费用奖励,他会把一个流量送过去,但是如果另一个点没有这个奖励就不会连过去,就会剩下一个流量,这个流量到哪里去了呢?可能用在别的边上面,他也只拿一个拥有费用奖励的点,然后一个本来满足不了限制条件的方案因为边和点错位了就满足限制条件了,就整个错误了。
解决这个问题就是要把一条边两个点要取全都取,要不取全都不取,但是我想了很久都没有想出来这个应该怎么解决,求助大家有没有什么解决办法!
回复
共 2 条回复,欢迎继续交流。
正在加载回复...