寒江陪烟火🔥

网络流

acm相关(6) dp(68) RMQ(5) STL(6) 主席树(2) 二分匹配(23) 二分查找(2) 分治法(3) 划分树(1) 单调队列(2) 博弈(11) 字典树(3) 字符串处理(1) 学习(1) 并查集(4) 强联通分量(3) 归并排序(1) 拓扑排序(1) 搜索(1) 数论(8) 最小生成树(3) 最短路(5) 树状数组(7) 树链剖分(4) 欧拉回路(5) 简单模版(14) 简单题(24) 线段树(13)

/ 注册

全部文章 / 网络流（共6篇）

HDU5988 Coding Contest（浮点费用流）

题意： n（100）个点，每个点有人数和食物数，m（5000）条边，每条边有有几率破坏网络，第一次走的话保证不会破坏网络，然后再走就会有p的概率破坏网络，每条边有最大走的次数c（100）。现在可以通过边来移动人，使得每个人都有食物，题目保证有解，问你破坏网络的最小概率思路：先把第一...

2016-11-27

0 304

upcoj2673 It Can Be Arranged（isap）

题意：有N节课，每节课有起止时间和学生数然后给你M是每个教室容纳的学生数然后给你n*n的矩阵表示上完第i节课然后上第j节课需要a[i][j]的时间调整第i节课结束时间加上调整时间要严格小于第j节课的开始时间问你最少需要多少个教室思路：很简单的一个最大流每节课分为两个节...

2016-09-09

0 258

POJ3762 The Bonus Salary! （费用流+离散化）

#include <iostream> #include <cstdio> #include <cstring> #include <string> #include <queue> #include <cmath> #incl...

2015-10-03

0 225

HDU1533 Going Home（最小费用最大流 spfa模版）

题意：给你一个N行M列的矩阵，其中“.”代表空地，“H”代表房子，“m”代表人，其中有n个房子和n个人。现在要求每个人进入一间房子，且人走一步需要支付1美元。求最小需要花费多少美元才能让所有人都进入到房子中（每个人只能进入一间房子，每个房子只能容纳一个人）。建图思路与安排工作那道题一样，...

2015-08-29

0 231

HDU3572 Task Schedule（ISAP）

学了几天的网络流，感觉还是ISAP算法比较实用，用这道题整理了一下，可以当作模版题意：给出n个任务+m台机器，还有一个任务处理时限+开始时间+结束时间，一个时刻里一台机器只能处理一个任务，但是一个任务可以在不同机器处理，问能否处理完所有任务？方法：最大流。这个题的建图算是经典，因为限定每个时...

2015-08-28

0 203

HDU1532（最大流模版题ek/dinic/isap）

就是由于下大雨的时候约翰的农场就会被雨水给淹没，无奈下约翰不得不修建水沟，而且是网络水沟，并且聪明的约翰还控制了水的流速，本题就是让你求出最大流速，无疑要运用到求最大流了。题中N为水沟数，M为水沟的顶点，接下来Si,Ei,Ci分别是水沟的起点，终点以及其容量。求源点1到终点M的最大流速。 ek: ...

2015-08-26

0 388