跪求大牛答疑【tjuacm吧】_百度贴吧

11月24日漏签0天

tjuacm吧关注：49贴子：303

7回复贴，共1页

<返回tjuacm吧

跪求大牛答疑

只看楼主收藏回复

有一个有向图，1000个点10000条边，求从S到T再回到S的最短路，要求不能通过一条边两次，怎么算？(可能无解)

送TA礼物

IP属地:北京

1楼2013-08-06 11:00回复

最小费用最大流?

2楼2013-08-06 11:48

收起回复

不感兴趣

开通SVIP免广告

有向的图怎么建图？

3楼2013-08-06 19:27

循环流，S到起点，终点到T，S到终点，起点到T。复杂度的话，不敢保证。

4楼2013-08-06 20:51

收起回复

那就S到起点，起点到T，把终点拆开，连一条流量为1，费用为-987654321的边就好了，那终点的那条边就肯定会流了。

5楼2013-08-07 10:03

收起回复

扫二维码下载贴吧客户端

下载贴吧APP
看高清直播、视频！

贴吧热议榜

7回复贴，共1页

<返回tjuacm吧

发表回复

发贴请遵守贴吧协议及“七条底线”贴吧投诉

内容:

使用签名档查看全部

发表

保存至快速回贴