网络流在游戏里面的应用

浮云半仙

其实我是来卖萌的(
见到最短路算法都在这里大放异彩，忍不住想来一发网络流
网络流是个什么问题呢，大概可以这样想象下:假设自来水公司的水有+oo之多并且水足够，现在水流经网络般复杂的自来水管，到达目的地，每秒钟能运送多少水量呢？(
在游戏里面我倒是更倾向用网络流做二分图匹配的应用，例如:
班上有n个同学，每个人都有一些希望能坐同桌的人，但是最终每个人只能选一个人坐同桌。现在老师知道每位同学都希望和哪些同学做同桌，那么老师最多能够满足多少位同学的心愿呢?
建立二分图，跑下最大流√ok。为什么请自行查询相关定理与资料。
再例如最小路径覆盖:给一个有向无环图图，求最少能使用多少条路径，不重不漏地覆盖整张图上所有的点？ 这里有讲解
最大流不过瘾还有最小费用最大流，还有带流量上下界的最大流.....
感觉会很有意思的。我就是来开脑洞的(逃

最大流实现代码:代码好像在这里显示有些问题，请点这里下载原文件: dinic.zip (884 Bytes, 下载次数: 82)

2016-11-17 00:21 上传

点击文件名下载附件

[pre lang="ruby" file="maxflow_dinic.rb"]#注意，运行过一次最大流之后会毁掉图的
class Dinic
    class Edge
        attr_accessor :from, :to, :rem
        def initialize(a, b, c)
            @from = a
            @to = b
            @rem = c
        end
    end
   
    attr_accessor :source, :sink
    attr_reader :graph, :edges
   
    def initialize(vs, sr, sk)  #顶点数,起点,终点
        @source = sr
        @sink = sk
        @graph = Array.new(vs+1) {Array.new}
        @edges = []
        
        #private
        @dist = Array.new(vs+1, 0)
        @vis = Array.new(vs+1, false)
        @q = Array.new(vs+1, nil)
    end
    def addedge(u, v, c)
        @edges.push(Edge.new(u, v, c))
        @edges.push(Edge.new(v, u, 0))
        @graph.push(@edges.size-2)
        @graph[v].push(@edges.size-1)
    end
    def bfs
        @vis.fill(false)
        @dist[@source] = 0
        head = 0
        tail = 1
        @q[head] = @source
        @vis[@source] = true
        while head < tail
            u = @q[tail-1]
            head += 1
            @graph.each do |i|
                e = @edges
                if !@vis[e.to] && e.rem > 0
                    @vis[e.to] = true
                    @dist[e.to] = @dist+1
                    @q[tail] = e.to
                    tail += 1
                end
            end
        end
        return @vis[@sink]
    end
    def dfs(u, flow)
        return flow if u == @sink || flow == 0
        n = 0
        r = 0
        @graph.each do |i|
            e = @edges
            if @dist[e.to] == @dist+1
                n = dfs(e.to, [flow, e.rem].min)
                next if n <= 0
               
                r += n
                e.rem -= n
                flow -= n
                @edges[i^1].rem += n
                break if flow == 0
            end
        end
        return r
    end
    def maxflow()
        r = 0
        r += dfs(@source, 0x7fffffff) while bfs
        r
    end
end

#test，正确答案为50
d = Dinic.new(4, 1, 4)
d.addedge(1, 2, 40)
d.addedge(1, 4, 20)
d.addedge(2, 4, 20)
d.addedge(2, 3, 30)
d.addedge(3, 4, 10)
puts d.maxflow  # => 50
[/pre]

唯道集虚

其实6R有关算法的帖子不算多，受众也不会太大，刚刚看到最短路径还是很惊讶的说。但如果把技术区的几个算法帖迁移过来，大概都能汇编起来了……看来是时候建立图书馆了（（
然而讲真 本蒟蒻对于算法和数据结构都是不太了解的 准备暑假学习的说
所以 还是不太明白的是网络流在实际开发游戏中有什么具体的应用呢？
当然，主要还是为了支持sxysxy的说～

shitake

这个0x7fffffff是什么鬼
ruby里有表示无穷大的常量（Float::INFINITY）
即使是要用自己定义的数值，最好的写法是将其定义成一个常量。
不然的话突然出现一个0x7fffffff严重影响代码的可读性。【简直magic number
还有记清楚你是在写ruby，而不是c。
这种“用某种语言的习惯去使用另外一种语言”习惯太坏了。

lcr

好厉害啊！ 虽然我看不明白代码，也不知道哪里开始学。