expect2004
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)
归档
标签
去牛客网
登录
/
注册
萌新expect的博客
由零至灵,由壹达意
全部文章
/ 网络流
(共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
438
LG1344 「USACO4.4」Pollutant Control 最小割
问题描述 LG1344 题解 我太菜了,我一开始竟然没有看出这是个最小割裸题。。。 两个询问。 第一个询问,直接跑最小割就好了。 第二个询问,建图的时候边权建 \(1\) ,代表割掉这条边需要 \(1\) 的代价。 \(\mathrm{Code}\) #include<...
2019-11-01
0
454
LG2770/LOJ6122 航空路线问题 费用流 网络流24题
问题描述 LG2770 LOG6122 题解 教训:关掉流同步之后就不要用其他输入输出方式了。 拆点。 两个拆点之间连\((1,1)\),其他连\((1,0)\) \(\mathrm{Code}\) #include<bits/stdc++.h> using na...
2019-09-20
0
422
LG2053/BZOJ1070 「SCOI2007」修车 费用流
问题描述 LG2053 BZOJ1070 题解 将\(m\)个修理工拆为\(n \times m\)个,将修理工和车辆看做二分图,连出一个完全二分图。 边流量为\(1\),费用为时间,费用流即可。 \(\mathrm{Code}\) #include<bits/stdc+...
2019-09-19
0
425
LG2045 方格取数加强版 费用流
问题描述 LG2045 题解 费用流。 套路拆点,把\((i,j)\)拆为两个点,在这两个点之间连边:一条边流量为\(1\),费用为\(a_{i,j}\),另一条边为流量为\(INF\),费用为\(0\)(表示联通)。 然后在\((i,j)\)的出点向\((i+1,j)\),\((i,...
2019-09-17
0
421
LG1640 「SCOI2010」连续攻击游戏 二分图最大匹配
问题描述 LG1640 题解 一开始以为是把\((a,b)\)作为左右部点,发现\(n \le 1000000\),建图是\(O(n^2)\)的,会爆掉 属性值向\(i\)建边。 \(\mathrm{Code}\) #include<bits/stdc++.h> us...
2019-09-16
0
480
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
425