(Solution:) 最大权闭合子图：给定一个有向图，点有点权，选择一个子图，满足子图上如果选择了一个点就必须选择它后继的所有点。最大化点权和。
不考虑租用机器时，(1.) (S) 向订单连流量为利润的边 (2.) 机器向 (T) 连流量为购买价格的边 (3.) 每个订单向需要的机器连流量为 (inf) 的边。
考虑租机器时，将订单向机器连边的流量改为租用价格。
signed main(){
read(n), read(m); memset(h, -1, sizeof h); S = 0, T = n + m + 1;
for(int i = 1, v, t, u, r; i
(Solution:) 假设 (m) 场全输，考虑 (i) 赢一场的贡献为 (C_i(a_i + 1)^2 + D_i(b_i – 1)^2 – C_i a_i^2 – D_ib_i^2=C_i + 2a_iC_i + D_i-2b_iD_i)。
(1.) (S) 连向 (m) 场比赛 ((1,0)) 的边 (2.) (m) 连向比赛相关两人 ((1,0)) 的边 (3.) 连人到 (T) 很多边，每条边为 ((1,C_i + 2a_iC_i + D_i-2b_iD_i)) 赢对应场数的贡献。
signed main(){
memset(h, -1, sizeof h); read(n), read(m); S = n + m + 1, T = S + 1;
for(int i = 1; i
(Solution:) (1.) ((S,i,va_i),(i,T,vb_i)) (2.) 对于城市之间 ((u,v,{ea\over 2} +{eb\over 2} + ec)) 双向边 (3.) ((S,u,{ea\over 2}),(S,v,{ea\over 2}),(u,T,{eb\over 2}),(v,T,{eb\over 2}))。
inline void add1(int a, int b, int c){
e[idx] = b, f[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}
signed main(){ memset(h, -1, sizeof h);
read(n), read(m); S = 0, T = n + 1; for(int i = 0; i > 1); add(S, v, x1 >> 1); add(u, T, x2 >> 1); add(v, T, x2 >> 1);
}n ++; print((sum - dinic()) >> 1); return 0;
}
(Problem:) 给定 (n) 个点 (m) 条有向边的图，只能由编号小的点走向编号大的点（走），边通过时间固定。还可以通过对于每个点用固定的时间从任一点到达该点（跳）。求从一没有连边的点出发遍历改图的最小时间。
(Solution:) 想象有 (n +1) 个人接力跑，分别站在 (S,1-n) 上，开始时接力棒在 (S) 手上，相当于选择起点。(S) 开始接力跑到达一个星球就停止，移交接力棒，该星球上的选手继续比赛，每个星球只能到一次，最大费用最小流。
(1.) ((S,1_x-n_x,1,0)) （等待接力） (2.) ((S,1_y-n_y,1,a_i))（跳）(3.) ((1_y-n_y,T,1,0)) （到达星球）(4.) ((u_x,v_y,1,w)) （走）。
signed main(){
read(n), read(m); memset(h, -1, sizeof h); S = 0, T = 2 * n + 1;
for(int i = 1; i v) swap(u, v); if(w < a[v]) add(u, n + v, 1, w); }
int flow, cost; EK(flow, cost); print(cost); return 0;
}
(Solution:) (1.) 将 (m) 位师傅拆为 (nm) 个点，点 ((i-1)n+j) 表示第 (i) 位师傅在修第 (j) 辆车，连向每辆车 ((1,k·c_{i,j}))(2.) ((S,m_i,1,0)) (3.) ((n_i · m_i,T,1,0))。
signed main(){
memset(h, -1, sizeof h); read(m), read(n); S = 0, T = n * m + n + 1;
for(int i = 1; i
(Problem:) (n) 道题, 第 (i) 天可以花费 (a_i) 准备一道题, 花费 (b_i) 打印一道题, 每天最多准备一道, 最多打印一道, 准备的题可以留到以后打印, 求最少花费使得准备并打印 (k) 道题。
(Solution:) 有一个显然的建图，(1.) (S) 向 (i) 连边，费用为 (a_i)，流量为 (1)。(2.) (i) 向 (T’) 连边，费用为 (b_i)，流量为 (1)。(3.) (i) 向 (i+1) 连边，费用为 (0)，流量为 (\inf)。(4.) (T’) 向 (T) 连边，费用为 (0)，流量为 (k)。
Original: https://www.cnblogs.com/William-Sg/p/16581606.html
Author: Altwilio
Title: 网络流做题记录
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/605275/
转载文章受原作者版权保护。转载请注明原作者出处！