热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

Dinic

1#include2#include3#include4#include5#include6#include7usingnamespacestd;89constintN210;10
,,
 1 #include 
 2 #include 
 3 #include 
 4 #include 
 5 #include 
 6 #include 
 7 using namespace std;
 8 
 9 const int N = 210;
10 const int M=1001000;
11 const int INF = 1001001010;
12 struct edge{
13     int u,v,cap,flow;
14     int next;
15 
16     //////
17 }e[M];
18 int head[N],num;
19 int cur[N],d[N];
20 bool vis[N];
21 int s,t;
22 void _add(int u,int v,int cap){
23     e[num].u = u;e[num].v = v;
24     e[num].cap = cap;e[num].flow = 0;
25     e[num].next = head[u];
26 
27     //////
28     head[u] = num++;
29 }
30 
31 void add(int u,int v,int cap){
32     _add(u,v,cap); _add(v,u,0);
33 }
34 
35 bool BFS(){
36     memset(vis,0,sizeof(vis));
37     queue<int> Q;
38     Q.push(s);
39     d[s] = 0;
40     vis[s]=1;
41     while(!Q.empty()){
42         int x = Q.front(); Q.pop();
43         for(int i = head[x]; i != -1;i = e[i].next){
44             if(!vis[e[i].v] && e[i].cap > e[i].flow ){
45                 vis[e[i].v] = 1;
46                 d[e[i].v] = d[x] + 1;
47                 Q.push(e[i].v);
48             }
49         }
50     }
51     return vis[t];
52 }
53 
54 int DFS(int x, int a){
55     if(x == t || a == 0) return a;
56     int flow=0,f;
57 
58     for(int &i = cur[x]; i != -1; i = e[i].next){
59         if(d[x] + 1 == d[e[i].v] && (f = DFS(e[i].v, min(a, e[i].cap - e[i].flow))) > 0){
60             e[i].flow += f;
61             e[i ^ 1].flow -= f;
62             flow += f;
63             a -= f;
64             if(a == 0)break;
65         }
66     }
67     return flow;
68 }
69 int Dinic(){
70     int flow = 0;
71     while(BFS()){
72         memcpy(cur,head,sizeof(head));
73         flow += DFS(s,INF);
74     }
75     return flow;
76 }
77 void init(int n){
78     memset(head,-1,sizeof(head));
79     num=0;
80 }
Dinic

无源无汇有下界可行流

t -> s 连一条 INF cap。

对于 边 u -> v ,下界 c1 ,上界 c2:

  s -> v    c1 

  u -> t    c1 

  u -> v   c2-c1

存在可行流的满足条件是 所有附加弧满载

Dinic


推荐阅读
  • [c++基础]STL
    cppfig15_10.cppincludeincludeusingnamespacestd;templatevoidprintVector(constvector&integer ... [详细]
  • 蒜头君的倒水问题(矩阵快速幂优化)
    蒜头君将两杯热水分别倒入两个杯子中,每杯水的初始量分别为a毫升和b毫升。为了使水冷却,蒜头君采用了一种特殊的方式,即每次将第一杯中的x%的水倒入第二杯,同时将第二杯中的y%的水倒入第一杯。这种操作会重复进行k次,最终求出两杯水中各自的水量。 ... [详细]
  • 使用 Git Rebase -i 合并多个提交
    在开发过程中,频繁的小改动往往会生成多个提交记录。为了保持代码仓库的整洁,我们可以使用 git rebase -i 命令将多个提交合并成一个。 ... [详细]
  • malloc 是 C 语言中的一个标准库函数,全称为 memory allocation,即动态内存分配。它用于在程序运行时申请一块指定大小的连续内存区域,并返回该区域的起始地址。当无法预先确定内存的具体位置时,可以通过 malloc 动态分配内存。 ... [详细]
  • NX二次开发:UFUN点收集器UF_UI_select_point_collection详解
    本文介绍了如何在NX中使用UFUN库进行点收集器的二次开发,包括必要的头文件包含、初始化和选择点集合的具体实现。 ... [详细]
  • 本文详细介绍了如何解决DNS服务器配置转发无法解析的问题,包括编辑主配置文件和重启域名服务的具体步骤。 ... [详细]
  • 经过一年的思考,我发现自己对开发的兴趣并不浓厚,而对算法研究则更加热衷。本文将探讨开发与算法之间的本质差异,并分享我的未来学习计划。 ... [详细]
  • 普通树(每个节点可以有任意数量的子节点)级序遍历 ... [详细]
  • 本文介绍了Java编程语言的基础知识,包括其历史背景、主要特性以及如何安装和配置JDK。此外,还详细讲解了如何编写和运行第一个Java程序,并简要介绍了Eclipse集成开发环境的安装和使用。 ... [详细]
  • 数据结构第三章,栈、队列、数组,期末不挂科指南,第3篇
    数据结构第三章,栈、队列、数组,期末不挂科指南,第3篇,Go语言社区,Golang程序员人脉社 ... [详细]
  • LDAP服务器配置与管理
    本文介绍如何通过安装和配置SSSD服务来统一管理用户账户信息,并实现其他系统的登录调用。通过图形化交互界面配置LDAP服务器,确保用户账户信息的集中管理和安全访问。 ... [详细]
  • 如果应用程序经常播放密集、急促而又短暂的音效(如游戏音效)那么使用MediaPlayer显得有些不太适合了。因为MediaPlayer存在如下缺点:1)延时时间较长,且资源占用率高 ... [详细]
  • 网络爬虫的规范与限制
    本文探讨了网络爬虫引发的问题及其解决方案,重点介绍了Robots协议的作用和使用方法,旨在为网络爬虫的合理使用提供指导。 ... [详细]
  • 本文介绍了 AngularJS 中的 $compile 服务及其用法,通过示例代码展示了如何使用 $compile 动态编译和链接 HTML 元素。 ... [详细]
  • 本文介绍如何使用线段树解决洛谷 P1531 我讨厌它问题,重点在于单点更新和区间查询最大值。 ... [详细]
author-avatar
mobiledu2502911637
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有