schtonn
/
public


			
							123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267
							<!DOCTYPE html>
<html>
<head>
  <meta charset="utf-8">
  

  <title>网络最大流-Dinic | Schtonn&#39;s Blog</title>
  <meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1">
  <meta name="description" content="前置知识
 存图方式（邻接表，邻接矩阵）,图的遍历（dfs，bfs）
 引入
 我们举个例子吧： 有一个毒瘤水管工，他会造水管，有一天他造了一个水管网络，就像一个图。其中有一个点只有出边，就是起点，还有一个点只有入边，是终点。 点之间有一些管子，这些管子都有单位时间内的容量，现在毒瘤水管工想知道，他的管子在单位时间内在起点终点之间最多能流多少水。">
<meta property="og:type" content="article">
<meta property="og:title" content="网络最大流-Dinic">
<meta property="og:url" content="http://yoursite.com/2020/03/02/dinic/index.html">
<meta property="og:site_name" content="Schtonn&#39;s Blog">
<meta property="og:description" content="前置知识
 存图方式（邻接表，邻接矩阵）,图的遍历（dfs，bfs）
 引入
 我们举个例子吧： 有一个毒瘤水管工，他会造水管，有一天他造了一个水管网络，就像一个图。其中有一个点只有出边，就是起点，还有一个点只有入边，是终点。 点之间有一些管子，这些管子都有单位时间内的容量，现在毒瘤水管工想知道，他的管子在单位时间内在起点终点之间最多能流多少水。">
<meta property="og:locale" content="en_US">
<meta property="og:image" content="https://img-blog.csdnimg.cn/20200111112801923.png">
<meta property="og:image" content="https://img-blog.csdnimg.cn/20200111114148208.png">
<meta property="og:image" content="https://img-blog.csdnimg.cn/20200111112801923.png">
<meta property="og:image" content="file://C:/Users/liangliang/Documents/Gridea/post-images/1582894458914.png">
<meta property="article:published_time" content="2020-03-02T03:31:22.000Z">
<meta property="article:modified_time" content="2020-03-03T12:41:19.240Z">
<meta property="article:author" content="Schtonn">
<meta property="article:tag" content="graph">
<meta name="twitter:card" content="summary">
<meta name="twitter:image" content="https://img-blog.csdnimg.cn/20200111112801923.png">
  
    <link rel="alternate" href="/atom.xml" title="Schtonn&#39;s Blog" type="application/atom+xml">
  
  
    <link rel="icon" href="/favicon.png">
  
  
    <link href="//fonts.googleapis.com/css?family=Source+Code+Pro" rel="stylesheet" type="text/css">
  
  
<link rel="stylesheet" href="/css/style.css">

<meta name="generator" content="Hexo 4.2.0"></head>

<body>
  <div id="container">
    <div id="wrap">
      <header id="header">
  <div id="banner"></div>
  <div id="header-outer" class="outer">
    <div id="header-title" class="inner">
      <h1 id="logo-wrap">
        <a href="/" id="logo">Schtonn&#39;s Blog</a>
      </h1>
      
        <h2 id="subtitle-wrap">
          <a href="/" id="subtitle">Schtonn&#39;s blog</a>
        </h2>
      
    </div>
    <div id="header-inner" class="inner">
      <nav id="main-nav">
        <a id="main-nav-toggle" class="nav-icon"></a>
        
          <a class="main-nav-link" href="/">Home</a>
        
          <a class="main-nav-link" href="/archives">Archives</a>
        
      </nav>
      <nav id="sub-nav">
        
          <a id="nav-rss-link" class="nav-icon" href="/atom.xml" title="RSS Feed"></a>
        
        <a id="nav-search-btn" class="nav-icon" title="Search"></a>
      </nav>
      <div id="search-form-wrap">
        <form action="//google.com/search" method="get" accept-charset="UTF-8" class="search-form"><input type="search" name="q" class="search-form-input" placeholder="Search"><button type="submit" class="search-form-submit">&#xF002;</button><input type="hidden" name="sitesearch" value="http://yoursite.com"></form>
      </div>
    </div>
  </div>
</header>
      <div class="outer">
        <section id="main"><article id="post-dinic" class="article article-type-post" itemscope itemprop="blogPost">
  <div class="article-meta">
    <a href="/2020/03/02/dinic/" class="article-date">
  <time datetime="2020-03-02T03:31:22.000Z" itemprop="datePublished">2020-Mar-02</time>
</a>
    
  </div>
  <div class="article-inner">
    
    
      <header class="article-header">
        
  
    <h1 class="article-title" itemprop="name">
      网络最大流-Dinic
    </h1>
  

      </header>
    
    <div class="article-entry" itemprop="articleBody">
      
        <h3 id="前置知识">前置知识</h3>
<p>存图方式（<a href="http://baidu.physton.com/?q=邻接表" target="_blank" rel="noopener" title="简单">邻接表</a>，<a href="http://baidu.physton.com/?q=邻接矩阵" target="_blank" rel="noopener" title="都太简单了">邻接矩阵</a>）,图的遍历（<a href="http://baidu.physton.com/?q=dfs" target="_blank" rel="noopener" title="简单">dfs</a>，<a href="http://baidu.physton.com/?q=bfs" target="_blank" rel="noopener" title="简单">bfs</a>）</p>
<h3 id="引入">引入</h3>
<p>我们举个例子吧： 有一个毒瘤水管工，他会造水管，有一天他造了一个水管网络，就像一个图。其中有一个点只有出边，就是起点，还有一个点只有入边，是终点。 点之间有一些管子，这些管子都有单位时间内的容量，现在毒瘤水管工想知道，他的管子在<strong>单位时间内</strong>在起点终点之间最多能流多少水。 <a id="more"></a></p>
<h3 id="概念">概念</h3>
<ul>
<li>源点：顾名思义，起点，一般用s表示</li>
<li>汇点：顾名思义，终点，一般用t表示。。。</li>
<li>容量：顾名思义。。。一条边单位时间内的的容量</li>
<li>残余网络：进行增广后剩余的网络</li>
<li>増广： &gt; 増广就是在残余网络中寻找从源点到汇点的可行路径（増广路），并将该路径上的所有边的容量减去路径中的最小容量，形成新的残余网络，<strong>人话就是找一条能走的路，然后把路走掉。</strong> 例如： <img src="https://img-blog.csdnimg.cn/20200111112801923.png" alt="在这里插入图片描述" /> 如果当前有这样一个残余网络，那么<span class="math inline">\(s\rightarrow4\rightarrow1\rightarrow t\)</span>就是一条増广路，最小容量是4，进行増广过后就形成了这样一张图： <img src="https://img-blog.csdnimg.cn/20200111114148208.png" alt="在这里插入图片描述" /> 如何寻找増广路？直接dfs即可。</li>
<li>反向边： &gt; 有时候，程序増广的时候会出现爆炸性错误，例如还是那个图： <img src="https://img-blog.csdnimg.cn/20200111112801923.png" alt="在这里插入图片描述" /> 有两条増广路，万一程序选错了怎么办？ 这时就要请出反向边了。 每次増广的时候，<strong>在残余网络上逆着増广路径建容量与増广路径最小容量相等的反向边</strong>，比如刚才那张图，就顺着<span class="math inline">\(t\rightarrow1\rightarrow4\rightarrow s\)</span>建容量为4的边。相当于把原来的那条路抵消掉了，如果増广时走过了反向边，就相当于把原来的増广撤回去了。 这就给了程序一个反悔的机会。</li>
</ul>
<h3 id="朴素算法">朴素算法</h3>
<ol type="1">
<li>増广</li>
<li>沿着増广路径建反向边</li>
<li>如果源点与汇点依然连通，回到1</li>
</ol>
<h3 id="dinic优化">Dinic优化</h3>
<p>Dinic的优化就是用bfs建立了由s开始的一个分层图，每次寻找増广路时必须让边上的层数严格递增，就可以确保每一步都离汇点近了一些这样就不会陷入毒瘤数据卡成的死循环，比如这样的著名毒瘤数据： <img src="file://C:/Users/liangliang/Documents/Gridea/post-images/1582894458914.png" />在这个数据中，如果用朴素算法，就会让中间容量为1的边上下抖动抽搐，等到他抽了999次的时候才把上面和下面的999减没。如果用Dinic，两次直接求出999+999。</p>
<h3 id="代码">代码</h3>
<p><a href="https://schtonn.github.io/404.html" target="_blank" rel="noopener"><code>404 Not Found(Click for more information)</code></a> 完结！</p>

      
    </div>
    <footer class="article-footer">
      <a data-url="http://yoursite.com/2020/03/02/dinic/" data-id="ck7cjuv6t0001pc135euzdup8" class="article-share-link">Share</a>
      
      
  <ul class="article-tag-list" itemprop="keywords"><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/graph/" rel="tag">graph</a></li></ul>

    </footer>
  </div>
  
    
<nav id="article-nav">
  
    <a href="/2020/03/02/ferbonacci/" id="article-nav-newer" class="article-nav-link-wrap">
      <strong class="article-nav-caption">Newer</strong>
      <div class="article-nav-title">
        
          斐波那契数列-O(1)
        
      </div>
    </a>
  
  
    <a href="/2020/03/01/min-span-tree/" id="article-nav-older" class="article-nav-link-wrap">
      <strong class="article-nav-caption">Older</strong>
      <div class="article-nav-title">最小生成树</div>
    </a>
  
</nav>

  
</article>

</section>
        
          <aside id="sidebar">
  
    
  <div class="widget-wrap">
    <h3 class="widget-title">Tags</h3>
    <div class="widget">
      <ul class="tag-list" itemprop="keywords"><li class="tag-list-item"><a class="tag-list-link" href="/tags/graph/" rel="tag">graph</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/math/" rel="tag">math</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/other/" rel="tag">other</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/struct/" rel="tag">struct</a></li></ul>
    </div>
  </div>


  <div class="widget-wrap">
    <h3 class="widget-title">Tag Cloud</h3>
    <div class="widget tagcloud">
      <a href="/tags/graph/" style="font-size: 20px;">graph</a> <a href="/tags/math/" style="font-size: 10px;">math</a> <a href="/tags/other/" style="font-size: 15px;">other</a> <a href="/tags/struct/" style="font-size: 10px;">struct</a>
    </div>
  </div>

  
  <div class="widget-wrap">
    <h3 class="widget-title">Archives</h3>
    <div class="widget">
      <ul class="archive-list"><li class="archive-list-item"><a class="archive-list-link" href="/archives/2020/03/">March 2020</a></li></ul>
    </div>
  </div>


  <div class="widget-wrap">
    <h3 class="widget-title">Recent Posts</h3>
    <div class="widget">
      <ul>
        
          <li>
            <a href="/2020/03/02/segment-tree/">线段树</a>
          </li>
        
          <li>
            <a href="/2020/03/02/ferbonacci/">斐波那契数列-O(1)</a>
          </li>
        
          <li>
            <a href="/2020/03/02/dinic/">网络最大流-Dinic</a>
          </li>
        
          <li>
            <a href="/2020/03/01/min-span-tree/">最小生成树</a>
          </li>
        
          <li>
            <a href="/2020/03/01/union-find/">并查集</a>
          </li>
        
      </ul>
    </div>
  </div>

  
</aside>
        
      </div>
      <footer id="footer">
  
  <div class="outer">
    <div id="footer-info" class="inner">
      &copy; 2020 Schtonn<br>
      Powered by <a href="http://hexo.io/" target="_blank">Hexo</a>
    </div>
  </div>
</footer>
    </div>
    <nav id="mobile-nav">
  
    <a href="/" class="mobile-nav-link">Home</a>
  
    <a href="/archives" class="mobile-nav-link">Archives</a>
  
</nav>
    

<script src="//ajax.googleapis.com/ajax/libs/jquery/2.0.3/jquery.min.js"></script>


<link rel="stylesheet" href="/fancybox/jquery.fancybox.css">

  
<script src="/fancybox/jquery.fancybox.pack.js"></script>


<script src="/js/script.js"></script>


  </div>
</body>
</html>