| 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427 |
- <!DOCTYPE html>
- <html lang="en">
- <head>
- <meta charset="UTF-8">
- <meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=2">
- <meta name="theme-color" content="#222">
- <meta name="generator" content="Hexo 4.2.0">
- <link rel="apple-touch-icon" sizes="180x180" href="/images/apple-touch-icon-next.png">
- <link rel="icon" type="image/png" sizes="32x32" href="/images/favicon-32x32-next.png">
- <link rel="icon" type="image/png" sizes="16x16" href="/images/favicon-16x16-next.png">
- <link rel="mask-icon" href="/images/logo.svg" color="#222">
- <link rel="stylesheet" href="/css/main.css">
- <link rel="stylesheet" href="/lib/font-awesome/css/font-awesome.min.css">
- <link rel="stylesheet" href="/lib/pace/pace-theme-minimal.min.css">
- <script src="/lib/pace/pace.min.js"></script>
- <script id="hexo-configurations">
- var NexT = window.NexT || {};
- var CONFIG = {"hostname":"yoursite.com","root":"/","scheme":"Muse","version":"7.7.2","exturl":false,"sidebar":{"position":"left","display":"post","padding":18,"offset":12,"onmobile":false},"copycode":{"enable":false,"show_result":false,"style":null},"back2top":{"enable":true,"sidebar":false,"scrollpercent":true},"bookmark":{"enable":false,"color":"#222","save":"auto"},"fancybox":false,"mediumzoom":false,"lazyload":false,"pangu":false,"comments":{"style":"tabs","active":null,"storage":true,"lazyload":false,"nav":null},"algolia":{"hits":{"per_page":10},"labels":{"input_placeholder":"Search for Posts","hits_empty":"We didn't find any results for the search: ${query}","hits_stats":"${hits} results found in ${time} ms"}},"localsearch":{"enable":false,"trigger":"auto","top_n_per_article":1,"unescape":false,"preload":false},"motion":{"enable":true,"async":false,"transition":{"post_block":"fadeIn","post_header":"slideDownIn","post_body":"slideDownIn","coll_header":"slideLeftIn","sidebar":"slideLeftIn"}}};
- </script>
- <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'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-03T09:49:05.954Z">
- <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="canonical" href="http://yoursite.com/2020/03/02/dinic/">
- <script id="page-configurations">
- // https://hexo.io/docs/variables.html
- CONFIG.page = {
- sidebar: "",
- isHome : false,
- isPost : true
- };
- </script>
- <title>网络最大流-Dinic | Schtonn's Blog</title>
-
- <noscript>
- <style>
- .use-motion .brand,
- .use-motion .menu-item,
- .sidebar-inner,
- .use-motion .post-block,
- .use-motion .pagination,
- .use-motion .comments,
- .use-motion .post-header,
- .use-motion .post-body,
- .use-motion .collection-header { opacity: initial; }
- .use-motion .site-title,
- .use-motion .site-subtitle {
- opacity: initial;
- top: initial;
- }
- .use-motion .logo-line-before i { left: initial; }
- .use-motion .logo-line-after i { right: initial; }
- </style>
- </noscript>
- </head>
- <body itemscope itemtype="http://schema.org/WebPage">
- <div class="container use-motion">
- <div class="headband"></div>
- <header class="header" itemscope itemtype="http://schema.org/WPHeader">
- <div class="header-inner"><div class="site-brand-container">
- <div class="site-nav-toggle">
- <div class="toggle" aria-label="Toggle navigation bar">
- <span class="toggle-line toggle-line-first"></span>
- <span class="toggle-line toggle-line-middle"></span>
- <span class="toggle-line toggle-line-last"></span>
- </div>
- </div>
- <div class="site-meta">
- <div>
- <a href="/" class="brand" rel="start">
- <span class="logo-line-before"><i></i></span>
- <span class="site-title">Schtonn's Blog</span>
- <span class="logo-line-after"><i></i></span>
- </a>
- </div>
- <p class="site-subtitle">Schtonn's blog</p>
- </div>
- <div class="site-nav-right">
- <div class="toggle popup-trigger">
- </div>
- </div>
- </div>
- <nav class="site-nav">
-
- <ul id="menu" class="menu">
- <li class="menu-item menu-item-home">
- <a href="/" rel="section"><i class="fa fa-fw fa-home"></i>Home</a>
- </li>
- <li class="menu-item menu-item-tags">
- <a href="/tags/" rel="section"><i class="fa fa-fw fa-tags"></i>Tags</a>
- </li>
- <li class="menu-item menu-item-archives">
- <a href="/archives/" rel="section"><i class="fa fa-fw fa-archive"></i>Archives</a>
- </li>
- </ul>
- </nav>
- </div>
- </header>
-
- <div class="back-to-top">
- <i class="fa fa-arrow-up"></i>
- <span>0%</span>
- </div>
- <div class="reading-progress-bar"></div>
- <main class="main">
- <div class="main-inner">
- <div class="content-wrap">
-
- <div class="content">
-
- <div class="posts-expand">
-
-
-
- <article itemscope itemtype="http://schema.org/Article" class="post-block " lang="en">
- <link itemprop="mainEntityOfPage" href="http://yoursite.com/2020/03/02/dinic/">
- <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
- <meta itemprop="image" content="/images/avatar.gif">
- <meta itemprop="name" content="Schtonn">
- <meta itemprop="description" content="">
- </span>
- <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
- <meta itemprop="name" content="Schtonn's Blog">
- </span>
- <header class="post-header">
- <h1 class="post-title" itemprop="name headline">
- 网络最大流-Dinic
- </h1>
- <div class="post-meta">
-
-
- <span class="post-meta-item">
- <span class="post-meta-item-icon">
- <i class="fa fa-calendar-o"></i>
- </span>
- <span class="post-meta-item-text">Posted on</span>
- <time title="Created: 2020-Mar-02 11:31:22" itemprop="dateCreated datePublished" datetime="2020-03-02T11:31:22+08:00">2020-Mar-02</time>
- </span>
- <span class="post-meta-item">
- <span class="post-meta-item-icon">
- <i class="fa fa-calendar-check-o"></i>
- </span>
- <span class="post-meta-item-text">Edited on</span>
- <time title="Modified: 2020-Mar-03 17:49:05" itemprop="dateModified" datetime="2020-03-03T17:49:05+08:00">2020-Mar-03</time>
- </span>
-
- </div>
- </header>
-
-
-
- <div class="post-body" itemprop="articleBody">
-
- <link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/katex@0.10.1/dist/katex.min.css" integrity="sha384-dbVIfZGuN1Yq7/1Ocstc1lUEm+AT+/rCkibIcC/OmWo5f0EA48Vf8CytHzGrSwbQ" crossorigin="anonymous"><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>
- <ul>
- <li>源点：顾名思义，起点，一般用s表示</li>
- <li>汇点：顾名思义，终点，一般用t表示。。。</li>
- <li>容量：顾名思义。。。一条边单位时间内的的容量</li>
- <li>残余网络：进行增广后剩余的网络</li>
- <li>増广： > 増广就是在残余网络中寻找从源点到汇点的可行路径（増广路），并将该路径上的所有边的容量减去路径中的最小容量，形成新的残余网络，<strong>人话就是找一条能走的路，然后把路走掉。</strong> 例如： <img src="https://img-blog.csdnimg.cn/20200111112801923.png" alt="在这里插入图片描述"> 如果当前有这样一个残余网络，那么<span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>s</mi><mo>→</mo><mn>4</mn><mo>→</mo><mn>1</mn><mo>→</mo><mi>t</mi></mrow><annotation encoding="application/x-tex">s\rightarrow4\rightarrow1\rightarrow t</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.43056em;vertical-align:0em;"></span><span class="mord mathdefault">s</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">→</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:0.64444em;vertical-align:0em;"></span><span class="mord">4</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">→</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:0.64444em;vertical-align:0em;"></span><span class="mord">1</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">→</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:0.61508em;vertical-align:0em;"></span><span class="mord mathdefault">t</span></span></span></span>就是一条増广路，最小容量是4，进行増广过后就形成了这样一张图： <img src="https://img-blog.csdnimg.cn/20200111114148208.png" alt="在这里插入图片描述"> 如何寻找増广路？直接dfs即可。</li>
- <li>反向边： > 有时候，程序増广的时候会出现爆炸性错误，例如还是那个图： <img src="https://img-blog.csdnimg.cn/20200111112801923.png" alt="在这里插入图片描述"> 有两条増广路，万一程序选错了怎么办？ 这时就要请出反向边了。 每次増广的时候，<strong>在残余网络上逆着増广路径建容量与増广路径最小容量相等的反向边</strong>，比如刚才那张图，就顺着<span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>t</mi><mo>→</mo><mn>1</mn><mo>→</mo><mn>4</mn><mo>→</mo><mi>s</mi></mrow><annotation encoding="application/x-tex">t\rightarrow1\rightarrow4\rightarrow s</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.61508em;vertical-align:0em;"></span><span class="mord mathdefault">t</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">→</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:0.64444em;vertical-align:0em;"></span><span class="mord">1</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">→</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:0.64444em;vertical-align:0em;"></span><span class="mord">4</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">→</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:0.43056em;vertical-align:0em;"></span><span class="mord mathdefault">s</span></span></span></span>建容量为4的边。相当于把原来的那条路抵消掉了，如果増广时走过了反向边，就相当于把原来的増广撤回去了。 这就给了程序一个反悔的机会。</li>
- </ul>
- <h3 id="朴素算法">朴素算法</h3>
- <ol type="1">
- <li>増广</li>
- <li>沿着増广路径建反向边</li>
- <li>如果源点与汇点依然连通，回到1 ### Dinic优化 Dinic的优化就是用bfs建立了由s开始的一个分层图，每次寻找増广路时必须让边上的层数严格递增，就可以确保每一步都离汇点近了一些这样就不会陷入毒瘤数据卡成的死循环，比如这样的著名毒瘤数据： <img src="file://C:/Users/liangliang/Documents/Gridea/post-images/1582894458914.png">在这个数据中，如果用朴素算法，就会让中间容量为1的边上下抖动抽搐，等到他抽了999次的时候才把上面和下面的999减没。如果用Dinic，两次直接求出999+999。 ### 代码 <a href="https://schtonn.github.io/404.html" target="_blank" rel="noopener"><code>404 Not Found(Click for more information)</code></a> 完结！</li>
- </ol>
- </div>
-
-
-
- <footer class="post-footer">
- <div class="post-tags">
- <a href="/tags/graph/" rel="tag"># graph</a>
- </div>
-
-
- <div class="post-nav">
- <div class="post-nav-item">
- <a href="/2020/03/01/min-span-tree/" rel="prev" title="最小生成树">
- <i class="fa fa-chevron-left"></i> 最小生成树
- </a></div>
- <div class="post-nav-item">
- <a href="/2020/03/02/ferbonacci/" rel="next" title="斐波那契数列-O(1)">
- 斐波那契数列-O(1) <i class="fa fa-chevron-right"></i>
- </a></div>
- </div>
- </footer>
-
- </article>
-
-
-
- </div>
- </div>
-
- <script>
- window.addEventListener('tabs:register', () => {
- let activeClass = CONFIG.comments.activeClass;
- if (CONFIG.comments.storage) {
- activeClass = localStorage.getItem('comments_active') || activeClass;
- }
- if (activeClass) {
- let activeTab = document.querySelector(`a[href="#comment-${activeClass}"]`);
- if (activeTab) {
- activeTab.click();
- }
- }
- });
- if (CONFIG.comments.storage) {
- window.addEventListener('tabs:click', event => {
- if (!event.target.matches('.tabs-comment .tab-content .tab-pane')) return;
- let commentClass = event.target.classList[1];
- localStorage.setItem('comments_active', commentClass);
- });
- }
- </script>
- </div>
-
-
- <div class="toggle sidebar-toggle">
- <span class="toggle-line toggle-line-first"></span>
- <span class="toggle-line toggle-line-middle"></span>
- <span class="toggle-line toggle-line-last"></span>
- </div>
- <aside class="sidebar">
- <div class="sidebar-inner">
- <ul class="sidebar-nav motion-element">
- <li class="sidebar-nav-toc">
- Table of Contents
- </li>
- <li class="sidebar-nav-overview">
- Overview
- </li>
- </ul>
- <!--noindex-->
- <div class="post-toc-wrap sidebar-panel">
- <div class="post-toc motion-element"><ol class="nav"><li class="nav-item nav-level-3"><a class="nav-link" href="#前置知识"><span class="nav-number">1.</span> <span class="nav-text">&#x524D;&#x7F6E;&#x77E5;&#x8BC6;</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#引入"><span class="nav-number">2.</span> <span class="nav-text">&#x5F15;&#x5165;</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#朴素算法"><span class="nav-number">3.</span> <span class="nav-text">&#x6734;&#x7D20;&#x7B97;&#x6CD5;</span></a></li></ol></div>
- </div>
- <!--/noindex-->
- <div class="site-overview-wrap sidebar-panel">
- <div class="site-author motion-element" itemprop="author" itemscope itemtype="http://schema.org/Person">
- <p class="site-author-name" itemprop="name">Schtonn</p>
- <div class="site-description" itemprop="description"></div>
- </div>
- <div class="site-state-wrap motion-element">
- <nav class="site-state">
- <div class="site-state-item site-state-posts">
- <a href="/archives/">
-
- <span class="site-state-item-count">9</span>
- <span class="site-state-item-name">posts</span>
- </a>
- </div>
- <div class="site-state-item site-state-tags">
- <a href="/tags/">
-
- <span class="site-state-item-count">4</span>
- <span class="site-state-item-name">tags</span></a>
- </div>
- </nav>
- </div>
- </div>
- <div id="treefrog" style="text-align: center;margin-top: 18px;">
- <!--<object type="application/x-shockwave-flash" style="outline:none;" data="/js/treefrog.swf?up_bodyColor=444444&up_pattern=0&up_flyColor=777777&up_tongueColor=333333&up_patternColor=000000&up_releaseFly=30&up_frogName=Froggie&up_backgroundImage=http://&up_bellySize=.5&up_footColor=444444&up_eyeColor=555555&up_backgroundColor=222222&" width="310" height="600"><param name="movie" value="http://cdn.abowman.com/widgets/treefrog/treefrog.swf?up_bodyColor=444444&up_pattern=0&up_flyColor=777777&up_tongueColor=333333&up_patternColor=000000&up_releaseFly=30&up_frogName=Froggie&up_backgroundImage=http://&up_bellySize=.5&up_footColor=444444&up_eyeColor=555555&up_backgroundColor=222222&"></param><param name="AllowScriptAccess" value="always"></param><param name="wmode" value="opaque"></param><param name="scale" value="noscale"/><param name="salign" value="tl"/></object>-->
- <object type="application/x-shockwave-flash" style="outline:none;" data="/js/treefrog.swf?up_bodyColor=444444&up_pattern=0&up_flyColor=777777&up_tongueColor=555555&up_patternColor=000000&up_releaseFly=0&up_frogName=Froggie&up_backgroundImage=http://&up_bellySize=.5&up_footColor=444444&up_eyeColor=444444&up_backgroundColor=222222&" width="310" height="600"><param name="movie" value="http://cdn.abowman.com/widgets/treefrog/treefrog.swf?up_bodyColor=444444&up_pattern=0&up_flyColor=777777&up_tongueColor=555555&up_patternColor=000000&up_releaseFly=0&up_frogName=Froggie&up_backgroundImage=http://&up_bellySize=.5&up_footColor=444444&up_eyeColor=444444&up_backgroundColor=222222&"></param><param name="AllowScriptAccess" value="always"></param><param name="wmode" value="opaque"></param><param name="scale" value="noscale"/><param name="salign" value="tl"/></object>
- </div>
- </div>
- </aside>
- <div id="sidebar-dimmer"></div>
- </div>
- </main>
- <footer class="footer">
- <div class="footer-inner">
-
- <div class="copyright">
-
- ©
- <span itemprop="copyrightYear">2020</span>
- <span class="with-love">
- <i class="fa fa-user"></i>
- </span>
- <span class="author" itemprop="copyrightHolder">Schtonn</span>
- </div>
- <div class="powered-by">Powered by <a href="https://hexo.io/" class="theme-link" rel="noopener" target="_blank">Hexo</a> v4.2.0
- </div>
- <span class="post-meta-divider">|</span>
- <div class="theme-info">Theme – <a href="https://muse.theme-next.org/" class="theme-link" rel="noopener" target="_blank">NexT.Muse</a> v7.7.2
- </div>
-
- </div>
- </footer>
- </div>
-
- <script src="/lib/anime.min.js"></script>
- <script src="/lib/velocity/velocity.min.js"></script>
- <script src="/lib/velocity/velocity.ui.min.js"></script>
- <script src="/js/utils.js"></script>
- <script src="/js/motion.js"></script>
- <script src="/js/schemes/muse.js"></script>
- <script src="/js/next-boot.js"></script>
-
-
-
- </body>
- </html>
|
