一个可能和network flow相关的问题 - CS版

本页内容为未名空间相应帖子的节选和存档，一周内的贴子最多显示50字，超过一周显示500字访问原贴

CS版 - 一个可能和network flow相关的问题

相关主题
● 问一个machine learning/SVM 问题	● 有人知道免费的min cost network flow solver么？
● 如何在一个连续点分布中求出最远的两点之间距离？	● 问大家一个有向图的问题
● c里面如何向屏幕固定一个点输出字符？	● Maximum Flow一章好多啊。。。。
● 想学下cloud，有什么比较好的书推荐吗？ (转载)	● 中华传统文化系列之一：道德德商
● cs选课求教！	● 所谓的神医就jb是joke
● 最近有什么关于information flow,covert channel的会	● 全明星赛
● 算一个图的max flow	● 求救--关于在Mac上如何 group firefox tabs?
● 一道本科生的工程题目，要用matlab求解 (转载)	● 又黄了一个房子，被rejected了

相关话题的讨论汇总
话题: 球队话题: flow话题: 网络话题: 2n话题: network

进入CS版参与讨论

(共1页)

b*****h
发帖数: 25

最近一门课要做一个项目，有若干备选的题目，下面一个感觉没啥特别好的思路。
有2n个大学球队，相互之间要主客场各赛一次。连续主场和连续客场要低于4场。要求排
一
个schedule，使得2n只球队的旅行距离最短。
偶想往network flow上靠
先不想优化有所的球队，先针对球队1。建了个如下的网络。这个网络分n层，
每层从球队1，有2n-1个有向箭头指向剩下的球队。剩余球队之间是双向。然后每只球队
（
包括球队1）各有一个有向箭头指向高一层球队1，然后重复相同的步骤，直到建立n-1层
网
络。除了第一层网络的球队1连到高一层网络的球队1的距离为0外，其他连接的点与点的
距
离为实际大学球队之间的距离。这样任何网络当中的流就可以看作球队1比赛历经的地点
。
如果把最下面那层的每个点都由一个点s射入，最上面一层都射向一个点d。这样让b1等于
1，b2等于－1。就肯定有个流，不过如果min c*f，肯定这个流就直接从点2到最下面一层
的球队1一路跑到最上面一层的球队1，然后在由点d流出。这样可以保证这个流是一笔画
，
但是可能只有N－1个弧有流。
还有就是把每层除了球队1外的相同球队射向一

(共1页)

进入CS版参与讨论

相关主题
● 又黄了一个房子，被rejected了	● cs选课求教！
● 贴一首非常好听的钢琴曲	● 最近有什么关于information flow,covert channel的会
● 弱问cabin air filter. upside down?	● 算一个图的max flow
● 世界杯今日闭幕，欧洲杯预选9月开踢	● 一道本科生的工程题目，要用matlab求解 (转载)
● 问一个machine learning/SVM 问题	● 有人知道免费的min cost network flow solver么？
● 如何在一个连续点分布中求出最远的两点之间距离？	● 问大家一个有向图的问题
● c里面如何向屏幕固定一个点输出字符？	● Maximum Flow一章好多啊。。。。
● 想学下cloud，有什么比较好的书推荐吗？ (转载)	● 中华传统文化系列之一：道德德商

相关话题的讨论汇总
话题: 球队话题: flow话题: 网络话题: 2n话题: network

#	版面	帖数(主题数)
-	全站	4871 (796)
1	Military	3777 (569)
2	Stock	341 (51)
3	Joke	117 (17)
4	History	116 (3)
5	Automobile	100 (9)
6	USANews	55 (9)
7	Midlife	45 (1)
8	Headline	41 (41)
9	Dreamer	33 (13)
10	FleaMarket	32 (20)
11	Living	30 (7)

boards

未名新帖统计// 7月16日

历史上的今天