expect2004

网络流 - 最小割

Codeforces Round(2) Contests(11) review(2) 其他(1) 动态规划(19) 动态规划 - 区间DP(3) 动态规划 - 期望与概率DP(1) 动态规划 - 树形DP(4) 动态规划 - 状压DP(1) 动态规划 - 线性DP(1) 动态规划 - 背包(2) 图论 - Tarjan(4) 图论 - 二分图判定(2) 图论 - 拓扑排序(1) 图论 - 最短路(1) 图论 - 生成树(3) 字符串 - AC自动机(2) 字符串 - KMP(2) 字符串 - 后缀数组（SA）(3) 字符串 - 字典树（Trie）(1) 数学 - 其他(2) 数学 - 多项式(3) 数学 - 组合计数(1) 数学 - 莫比乌斯反演(2) 数学 - 高斯消元(2) 数据结构 - 分块(1) 数据结构 - 平衡树(1) 数据结构 - 树状数组(1) 数据结构 - 树链剖分(2) 数据结构 - 珂朵莉树(2) 数据结构 - 线段树(6) 数据结构 - 虚树(1) 未归档(6) 模板(5) 游记(3) 算法 - 2-SAT(2) 算法 - CDQ分治(1) 算法 - 搜索(2) 算法 - 树分治(2) 算法 - 矩阵树定理(1) 网络流(7) 网络流 - 二分图相关(1) 网络流 - 最大流(1) 题解(22)

/ 注册

全部文章 / 网络流 - 最小割（共6篇）

BZOJ2127/LG1646 happiness 新建点最小割

问题描述 BZOJ2127 LG1646 题解和文理分科差不多收益最大 -> 损失最小 -> 最小割分别新建点表示互相关系就行了 \(\mathrm{Code}\) #include<bits/stdc++.h> using namespace ...

2019-12-21

0 482

BZOJ3894/LG4313 文理分科新建点最小割

问题描述 BZOJ3894 LG4313 题解显然一个人只能选文/理 -> 一个人只能属于文（S）、理（T）集合中的一个可以把选择文得到 \(art\) 的收益看做选择文失去 \(science\) 的收益，也就是最小割了。考虑如何处理周围人都选对于文科，再新建一个 ...

2019-12-21

0 468

TopCoder12727 「SRM590Hard」FoxAndCity 最小割离散变量模型

问题描述一张 \(N\) 个点无向图，边权都为 \(1\) ，添加若干条边，最小化 \(\sum\limits_{1 \le i \le n,i \in N_{+}}{(a_i-b_i)^2}\)。 \(b_i\) 是输入的， \(a_i\) 是 \(1\) 号点到 \(i\) 号点的最短路。 ...

2019-12-21

0 725

BZOJ1391/LG4177 「CEOI2008」order 最大权闭合子图

问题描述 BZOJ1391 LG4177 题解最大权闭合子图，本质是最小割在任务和机器中间的边之前权值设为INF，代表不可违背这条规则本题的租借就相当于允许付出一定代价，违背某个规则，只需要把中间的边权改为代价即可。 \(\mathrm{Code}\) #inclu...

2019-12-14

0 594

BZOJ2007/LG2046 「NOI2010」海拔平面图最小割转对偶图最短路

问题描述 BZOJ2007 LG2046 题解发现左上角海拔为 \(0\) ，右上角海拔为 \(1\) 。上坡要付出代价，下坡没有收益，所以有坡度的路越少越好。所以海拔为 \(1\) 的点，和海拔为 \(0\) 的点，一定能够在这个网格图中由一条连续的线划分为两个集合。将一...

2019-12-14

0 557

BZOJ1001/LG4001 「ICPC Beijing2006」狼抓兔子平面图最小割转对偶图最短路

问题描述 BZOJ1001 LG4001 题解平面图最小割=对偶图最短路假设起点和终点间有和其他边都不相交的一条虚边。如图，平面图的若干条边将一个平面划分为若干个图形，每个图形就是对偶图中的一个点。对偶图中的每一个点，和它在平面图中每一个相邻的图形间有边，边权为原来分开...

2019-12-14

0 817