网络流

POJ1273，Drainage Ditches（最大流问题）

网络流最大流问题， Dinic与ISAP模板题。关于Dinic与ISAP的讲解可参考： https://zhuanlan.zhihu.com/p/46039732 https://blog.csdn.net/qq_34374664/article/details/75394588 Dinic AC代码： #include<cstdio> #include<algorithm…

POJ3436，ACM Computer Factory（最大流）

题意：一家电脑厂里，有N台组装电脑的机器，电脑由P个零件组成，每台机器有in[P]和out[P]两个参数，表示该机器需要in[P]所指示的零件，产出out[P]所指示的零件，同时每台机器每小时最多产出Q[i]组out[…

最小费用最大流问题（证明）

在网上翻了很久，终于找到一个大概看得懂的证明了。 https://bartholomewa.wordpress.com/2018/04/25/最小费用最大流详解模板/

POJ3281，Dining（二分匹配）

不难看出，这道题属于网络流的二分匹配应用，不过，在建模的时候要小心注意一点。此题当中有两个二分图，分别是1 ~ n->1 ~ f, 1 ~n -> 1 ~ d，建模要把两个二分图给联系，同时应建模过程中要注意&#xff…

GDKOI2016 Day1 T3 寻宝

T3 寻宝给出N个点，点与点之间有依赖关系，形如选了这个点，必须要选哪些点。每个点有两个权，a和b，求选出一些合法的点集，使得∑bi∑ai最小化。若无解则输出一个奇怪的字符串。 01分数规划。如果答案是l&…

网络流算法学习笔记——Dinic有效算法

屈婉玲《算法设计与分析》第2版第7章网络流算法学习笔记。概述 Dinic有效算法同样用来求最大流，相当于FF算法的改进。 FF算法参考：网络流算法学习笔记——最大流问题基本概念和Ford-Fulkerson方法（标号法C实现） 改进之处有&a…

【NOI2014模拟6.30】Honor

Description n个班级，每个班有m个学生。每个学生有一个给定的权值（可正可负），每个班级从头依次取若干个学生，有些班级之间有约束条件：班级a的人数多于班级b的人数不能超过c。总共有q个约束。求学生权值和的…

bzoj 1475: 方格取数

Description 在一个n*n的方格里，每个格子里都有一个正整数。从中取出若干数，使得任意两个取出的数所在格子没有公共边，且取出的数的总和尽量大。Input 第一行一个数n；（n<30） 接下来n行每行n个数描述一个…

[bzoj3144]【HNOI2013】切糕

Description 表示语文不好，看了好久才看懂题。化简之后的题意大概是这样的：给出一个P*Q的网格，在（x,y）放一个数字z（1<z<R）的代价是v(x,y,z)，并且四相邻中格子的数的绝对值差…

bzoj 3993: [Sdoi2015]星际战争

Description 3333年，在银河系的某星球上，X军团和Y军团正在激烈地作战。在战斗的某一阶段，Y军团一共派遣了N个巨型机器人进攻X军团的阵地，其中第i个巨型机器人的装甲值为Ai。当一个巨型机器人的装甲值减少到0或者以下时&#xff0c…

上下界网络流学习小记

写在前面网络流是信息学竞赛中几乎必考的一个模型。而上下界网络流也是网络流问题中的一个大类，出题很灵活。今年冬天第一次接触上下界之后果断滚粗，于是便恶补了一下上下界，大体有两种方法。可行流首先建立超级源和超级汇&#xff0…

bzoj 2400: Spoj 839 Optimal Marks

Description 定义无向图中的一条边的值为：这条边连接的两个点的值的异或值。定义一个无向图的值为：这个无向图所有边的值的和。给你一个有n个结点m条边的无向图。其中的一些点的值是给定的，而其余的点的值由你决定（但要求均为非负…

bzoj 1433: [ZJOI2009]假期的宿舍

Description Input Output Sample Input 1 3 1 1 0 0 1 0 0 1 1 1 0 0 1 0 0Sample Output ˆ ˆ HINT 对于30% 的数据满足1 ≤ n ≤ 12。对于100% 的数据满足1 ≤ n ≤ 50,1 ≤ T ≤ 20。网络流模板题。也可以用二分图匹配来做。源连有床位的i 要住宿的j连向汇然后认识的互…

bzoj 1565: [NOI2009]植物大战僵尸

Description Input Output 仅包含一个整数，表示可以获得的最大能源收入。注意，你也可以选择不进行任何攻击，这样能源收入为0。Sample Input 3 2 10 0 20 0 -10 0 -5 1 0 0 100 1 2 1 100 0 Sample Output 25 HINT 在样例中, 植物P1,1可以攻击…

网络流总结

【算法简介】网络流是个好东西主要掌握dinic的写法（最好是带上各种优化的）后，就是各种建图的套路了直接放个dinic的板子 const ll inf1e17; int head[maxn],tot1,cur[maxn]; struct edge {int to,nxt;ll v; }e[maxm<<1]; void ad…

SPOJ962:Intergalactic Map(最大流)

传送门题意： 在一个无向图中，一个人要从1点赶往2点，之后再赶往3点，且要求中途不能多次经过同一个点。问是否存在这样的路线。题解： 将题意转化，即求从2到1,3的两条不同路径。因为是点只能走一次&a…

【网络流】bzoj2095混合图欧拉回路

考虑到满足欧拉回路的条件是每个点的入度和出度相等。答案可以二分，对于每个mid建图。我们考虑如下的建图方式，先把所有的无向边随意定向，计算点的度数。如果此时有奇数度数的点，那么就肯定不存在欧拉回路。 S向入度<出度…

HDU - 4289 Control （最小割+建图+拆点）

链接：https://cn.vjudge.net/problem/HDU-4289 题意：多组样例。每组样例第一行给出n和m（n个城市，m条路相连）。接下来一行给出s（源点）和t（汇点）。接下来一行n个数&#x…

点向行列连边的网络流图优化成行列连边的二分图：CF1592F2

https://www.luogu.com.cn/problem/CF1592F2 做完F1，然后用1的结论来思考。场上推了几个性质。首先op4的操作行列必然两两不同，所以op4最多 max ⁡ ( n , m ) \max(n,m) max(n,m) 次。然后手玩发现只有除 ( n , m ) (n,m) (n,m) 的三个格子都为1&am…

ACM网络流模板

前言网络流是ACM图论中比较重要且难懂的一块。网络流的最经典应用就是最大流，求解网络流的基本思想就是每次寻找增广路。相关定义源点：有n个点，有m条有向边，有一个点很特殊，只出不进，叫做源点汇点&…

多次跑网络流（用于构造类）+霍尔定理证明可行：AGC317G

https://atcoder.jp/contests/abc317/tasks/abc317_g 一个很显然的思路，就是行向颜色连边，但约束条件展现出多个维度，所以可以考虑跑多次网络流。但跑同样的网络流没有意义，所以每次跑完都要在残余网络上操作一下才可行。此题中…

【笔记】网络流算法模板

文章目录 EK求最大流题目描述输入格式输出格式数据范围算法步骤算法时间复杂度 O ( n m 2 ) O(nm^2) O(nm2) AC CodeDinic/ISAP求最大流题目描述输入格式输出格式数据范围算法步骤算法时间复杂度 O ( n 2 m ) O(n^2m) O(n2m) AC CodeDinic/ISAP求最小割EK求费用流题目描述输…

AcWing算法进阶课-1.1.2Dinic/ISAP求最大流

算法进阶课整理 CSDN个人主页：更好的阅读体验原题链接题目描述给定一个包含 n n n 个点 m m m 条边的有向图，并给定每条边的容量，边的容量非负。图中可能存在重边和自环。求从点 S S S 到点 T T T 的最大流。输入格式第一行包…

$2021——网络流例题$

2021——网络流例题

1.hdu3987 Harry Potter and the Forbidden Forest 这道题目有双向边和单向边，破坏一条边的代价为Wi，求破坏的总代价最小的情况下，最少要破坏几条道路，使得城市0无法到达城市n-1 就是求0-（n-1）的最小割这…

网络流最大流初步-Push–relabel maximum flow algorithm

简介做网络流最大流的题，常用的算法就是Dinics algorithm。时间复杂度为,通常由于出题人水平较低，几乎能过所有的题。功利地看，这样就没问题了。但是，站在追求真（zhuang）理（B）的角…

网络流各种题型应用及解决方法

从浅到深，尽量每种题型都选出至少一道例题。代码在这-> 点击打开链接 1.最大流问题，s到t最大流为t到s最小流，最小割即最大流，求最小割割边也可以在网络流中实现，附一带求割边代码 #include<iostream> #inclu…

网络流24题——P1251餐巾计划问题

考虑到每天的干净餐巾和脏的餐巾是不同的，所以我们需要把每一天拆成两个点来处理，记作上午和下午想到这里问题就简单了建图： 源点向上午连(inf,p) 表示新买 // 源点向下午连(ri,0) 表示提供 // 上午到汇点连(ri,0) 来限制每天必须达到…

网络流_最大流_POJ 3281

题目链接：http://poj.org/problem?id3281 个人认为这个题的难点就在于见图，应为有多个源点和起点，所以我们可以设置一个超级源点和超级汇点将牛分1为2，一个牛吃菜，一个牛吃草，两个牛之间一一对应&#…

牛客练习赛53 德育分博弈政治课【网络流】

题目大意给出n个只有六个面的骰子每个面由1~9 中的数字组成每个面的数字不同给出q次询问每次给出一个串， 要求用n个骰子摆出串的形状题目分析因为每个骰子只能表示一个面类似一个由限制的问题考虑网络流中的一个点如果它的进入的流量为1 就能限制它在与…

【GDOI2017模拟8.11】生物学家

继续补。 Description 有n头牛，每头牛的性别已知。让第i头牛变性的代价为vi。有m个人，第i个人想要ki头牛的性别都是他自己选定的那个（雌性或雄性），如果这样你会获得wi的收益。如果不满足有些人的需求，他…

bzoj 2132: 圈地计划

Description 最近房地产商GDOI(Group of Dumbbells Or Idiots)从NOI(Nuts Old Idiots)手中得到了一块开发土地。据了解，这块土地是一块矩形的区域，可以纵横划分为NM块小区域。GDOI要求将这些区域分为商业区和工业区来开发。根据不同的地形环境&#xff0…

2016多校训练Contest4: 1009 String problem hdu5772

给你一个数字串，选某些位置有一个价值。选某些数字又有一些花费问你最大可以获得的价值看了下数据范围和价值计算的公式，基本是网络流问题没跑了。那么如何构图呢先对于每个数字k单独建立一个点，value-（b[k]-a[k]&#xff…

bzoj 3894: 文理分科

Description 文理分科是一件很纠结的事情！（虽然看到这个题目的人肯定都没有纠结过）小P所在的班级要进行文理分科。他的班级可以用一个n*m的矩阵进行描述，每个格子代表一个同学的座位。每位同学必须从文科和理科中选择一科。同学们…

POJ1459, Power Network（最大流）

用网络流最大流算法解决。本题看似有多个源点（发电站np）和多个汇点（用户nc），其实不然，我们只需添加s源点，t汇点，s连接np各点，其权值为发电量，nc各点连接t&am…

bzoj3638【GDOI2016模拟3.20】diyiti

Description 给出一个长度为n的序列，a1~an，和m次操作，每次操作分为 0 x val，将ax变成val 1 l r k，询问在区间l~r中，最多k个不重合区间的最大和是多少。 n,m<10^5，|ai|<500&#xff0c…

bzoj 1266: [AHOI2006]上学路线route

Description 可可和卡卡家住合肥市的东郊，每天上学他们都要转车多次才能到达市区西端的学校。直到有一天他们两人参加了学校的信息学奥林匹克竞赛小组才发现每天上学的乘车路线不一定是最优的。可可：“很可能我们在上学的路途上浪费了大量的时间&#x…

bzoj 3931: [CQOI2015]网络吞吐量

题目描述路由是指通过计算机网络把信息从源地址传输到目的地址的活动，也是计算机网络设计中的重点和难点。网络中实现路由转发的硬件设备称为路由器。为了使数据包最快的到达目的地，路由器需要选择最优的路径转发数据包。例如，在常用的路由算…

bzoj 2127: happiness

Description 高一一班的座位表是个n*m的矩阵，经过一个学期的相处，每个同学和前后左右相邻的同学互相成为了好朋友。这学期要分文理科了，每个同学对于选择文科与理科有着自己的喜悦值，而一对好朋友如果能同时选文科或者理科&#x…

最小费用流的最短路径算法和Ford单源最短路径算法（图解）

屈婉玲《算法设计与分析》第2版第7章网络流算法学习笔记。概述最小费用流的负回路算法，是先任意分配流量v0，再将流量调整到权值较小的边上，参考： 基于Floyd算法的最小费用流的负回路算法（图解） 而最小…

[bzoj1001][BeiJing2006]狼抓兔子

Description 给出一张网格，左上角点为(1,1),右下角点为(N,M).有以下三种类型的道路 1:(x,y)<>(x1,y) 2:(x,y)<>(x,y1) 3:(x,y)<>(x1,y1) 截断一条边的代价为它的权值，求最小的代价使得从左上角不可到达右下角。 Solution 很明显…

【GDSOI2018模拟4.19】排列

Description 有 n 个数 x1 ~xn 。你需要找出它们的一个排列，满足 m 个条件，每个条件形如 x_a 必须在x_b之前。在此基础上，你要最大化这个排列的最大子段和。 n<500 Solution 神仙题神奇的网络流建模，强行把两个最大权闭合…

bzoj 2718: [Violet 4]毕业旅行

Description Input Output 最多可选多少景点 Sample Input 7 6 1 2 2 3 5 4 4 3 3 6 6 7 Sample Output 2 HINT Source Ctsc2008 River & ural 1533. Fat Hobbits 首先有个结论。。最小路径覆盖n-最大二分图匹配然后这题就没了。。。记得floyd处理下联通刚好练了一下网络流…

AcWing算法进阶课-1.9.1Dinic/ISAP求最小割

算法进阶课整理 CSDN个人主页：更好的阅读体验原题链接题目描述给定一个包含 n n n 个点 m m m 条边的有向图，并给定每条边的容量，边的容量非负。图中可能存在重边和自环。求从点 S S S 到点 T T T 的最小割。输入格式第一行包…

【网络流】CF311E Biologist

题意有一个长度为n的01串，将第i个位置变为另外一个数字的代价是vi 。有m个要求每个要求的形式是首先确定若干位置都要是0 或者1 然后给定这K 个位置，如果些位置上都满足要求那么就可以得Wk 元某些要求如果失败了还要倒着给g 元问最终能够得到…

【洛谷P1231】教辅的组成

题目背景滚粗了的HansBug在收拾旧语文书，然而他发现了什么奇妙的东西。题目描述蒟蒻HansBug在一本语文书里面发现了一本答案，然而他却明明记得这书应该还包含一份练习题。然而出现在他眼前的书多得数不胜数，其中有书，有答案…

网络流建模汇总

因为网上Dinic模板大多不规范或者可以被卡，所以先贴出一份跑得比较快的Dinic模板（主要快在maxflow()里面，可以仔细体会）。 struct newG{int g[Maxn],v[Maxm],c[Maxm],nt[Maxm],cur[Maxn],lev[Maxn],ec;queue<int>q;inline …

[JZOJ5137]养猫

Description 你养了一只猫，一天被划分成n个时刻，每个时刻这只猫都可以选择睡觉或进食第i个时刻如果选择睡觉则会获得si的愉悦度，否则会获得ei的愉悦度对于每个长度为k的时刻区间，猫必须有至少min_sleep的时刻选择睡觉&#xff…

poj1637:Sightseeing tour(混合图欧拉回路，网络流)

传送门题意：判断混合图是否存在欧拉回路。真是一道好题。把该图的无向边随便定向， 计算每个点的入度和出度。如果有某个点出入度之差为奇数，那么肯定不存在欧拉回路。因为欧拉回路要求每点入度出度，也就是总度数为偶数&…

【题解】试题库问题

题意： 原题传送门思路按照最大流的日常套路，我们来考虑如何建图。显然我们把题的类型和每套试题分别作为图中的点。用编号为1~n的点表示n套试题，编号为n1~nk的点表示k种类型。由于每套试题贡献为1，那么我们就从试题向它所…

【题解】方格取数骑士共存问题（二分图最大独立集）

方格取数问题传送门骑士共存问题传送门分析之所以把这两题放在一起，是因为它们有很多的共同点。单看题目背景就知道其实它们挺类似的：都是在棋盘（网格）中，且点与点之间有相互的排斥关系。实际上它们的解法思想…

Gym 100203 I. WIN（网络流最大流）

题目链接:http://codeforces.com/gym/100203/problem/I 题意：给一个由W,I,N三种字母组成的n*m的矩阵，现在要从中截取 WIN ，要求I一定要在W和N的中间，问最多能截取多少个WIN。当然截取的意思就是一个字母用了一次就没有了&#…

【题解】魔术球问题

题意原题传送门。思路一看标签：网络流24题。我们考虑建图，把每个点拆开，若两个数和为平方数，那么就从编号小的向编号大的连权值为1的有向边。那么就把这个问题转换成了匹配问题。然后我们考虑对于一个新的球&#xff0c…

$2021——网络流初步$