网络流在游戏里面的应用

浮云半仙

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

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

2016-11-17 00:21 上传

点击文件名下载附件

RUBY 代码复制下载

#注意，运行过一次最大流之后会毁掉图的
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)  #顶点数,起点,终点
        [url=home.php?mod=space&uid=171370]@source[/url] = 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[u].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[u].each do |i|
                e = @edges[i]
                if !@vis[e.to] && e.rem > 0
                    @vis[e.to] = true
                    @dist[e.to] = @dist[u]+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[u].each do |i|
            e = @edges[i]
            if @dist[e.to] == @dist[u]+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

#注意，运行过一次最大流之后会毁掉图的


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)  #顶点数,起点,终点


        [url=home.php?mod=space&uid=171370]@source[/url] = 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[u].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[u].each do |i|


                e = @edges[i]


                if !@vis[e.to] && e.rem > 0


                    @vis[e.to] = true


                    @dist[e.to] = @dist[u]+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[u].each do |i|


            e = @edges[i]


            if @dist[e.to] == @dist[u]+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

唯道集虚

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

shitake

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

lcr

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