程序设计的题:
一图
一源点
一汇点
如何求出割集？ 就是哪些边是割边 求出来...
求算法思路
如何求网络流里面的割集?
答案:2 悬赏:20 手机版
解决时间 2021-01-29 10:39
- 提问者网友：寂寞梧桐
- 2021-01-29 01:26
最佳答案
- 五星知识达人网友：持酒劝斜阳
- 2021-01-29 02:56
先求网络流，得到残量网络，在参量网络中，从源出发，能够访问到的节点构成集合S，原图中从S到V-S的边即为割边。
全部回答
- 1楼网友：归鹤鸣
- 2021-01-29 03:11
首先来解释割集
在一个有权图中，源点为vs，汇点为vt，从vs到vt有很多路径可以走，每条路径都包含若干条边对吧。这些边可能只属于一条路径，也可能同时出现在两条路径中。 如果拿掉这张图中的一些边，就无法从vs到达vt，这些边的组合就叫做 割集。
最小割的解释：
割集有很多，每一个割集中元素的权值之和成为割集容量。 所有割集容量中，最小的那个割集就叫做最小割。
^^
我要举报
如以上问答信息为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！
大家都在看
推荐资讯