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) 网络流 - 二分图相关(1) 网络流 - 最大流(1) 网络流 - 最小割(6) 题解(22)

/ 注册

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

LG1345 「USACO5.4」Telecowmunication 最小割

问题描述 LG1345 题解点边转化，最小割，完事。 \(\mathrm{Code}\) #include<bits/stdc++.h> using namespace std; template <typename Tp> void read(Tp &...

2019-11-01

0 345

LG1344 「USACO4.4」Pollutant Control 最小割

问题描述 LG1344 题解我太菜了，我一开始竟然没有看出这是个最小割裸题。。。两个询问。第一个询问，直接跑最小割就好了。第二个询问，建图的时候边权建 \(1\) ，代表割掉这条边需要 \(1\) 的代价。 \(\mathrm{Code}\) #include<...

2019-11-01

0 319

LG2770/LOJ6122 航空路线问题费用流网络流24题

问题描述 LG2770 LOG6122 题解教训：关掉流同步之后就不要用其他输入输出方式了。拆点。两个拆点之间连\((1,1)\)，其他连\((1,0)\) \(\mathrm{Code}\) #include<bits/stdc++.h> using na...

2019-09-20

0 319

LG2053/BZOJ1070 「SCOI2007」修车费用流

问题描述 LG2053 BZOJ1070 题解将\(m\)个修理工拆为\(n \times m\)个，将修理工和车辆看做二分图，连出一个完全二分图。边流量为\(1\)，费用为时间，费用流即可。 \(\mathrm{Code}\) #include<bits/stdc+...

2019-09-19

0 316

LG2045 方格取数加强版费用流

问题描述 LG2045 题解费用流。套路拆点，把\((i,j)\)拆为两个点，在这两个点之间连边：一条边流量为\(1\)，费用为\(a_{i,j}\)，另一条边为流量为\(INF\)，费用为\(0\)（表示联通）。然后在\((i,j)\)的出点向\((i+1,j)\)，\((i,...

2019-09-17

0 304

LG1640 「SCOI2010」连续攻击游戏二分图最大匹配

问题描述 LG1640 题解一开始以为是把\((a,b)\)作为左右部点，发现\(n \le 1000000\)，建图是\(O(n^2)\)的，会爆掉属性值向\(i\)建边。 \(\mathrm{Code}\) #include<bits/stdc++.h> us...

2019-09-16

0 390

LG2598/BZOJ1412 「ZJOI2009」狼和羊的故事最小割

问题描述 LG2598 BZOJ1412 题解看到要把狼和羊两个物种分开自然想到最小割。发现\((x,y)\)可以向上下左右走以获得贡献，所以建边：\((x,y),(x-1,y)\),\((x,y),(x,y-1)\),\((x,y),(x,y+1)\),\((x,y),(x+...

2019-09-13

0 349