网络最大流
最大流 Dinic 板子：
bool bfs(){
memset(dep,0,sizeof(dep));
while(!q.empty()) q.pop();
q.push(s); dep[s]=1; nw[s]=hd[s];
while(!q.empty()){
int x=q.front(); q.pop();
for(int i=hd[x];i;i=eg[i].nxt){
int y=eg[i].v;
if(dep[y]||!eg[i].w) continue;
q.push(y); nw[y]=hd[y]; dep[y]=dep[x]+1;
if(y==t) return true;
}
}
return false;
}
int dfs(int x,int flow){
if(x==t) return flow;
int rst=flow,i,tmp;
for(i=nw[x];i&&rst;i=eg[i].nxt){
int y=eg[i].v; nw[x]=i; //注意当前弧优化！
if(!eg[i].w||dep[y]!=dep[x]+1) continue;
tmp=dfs(y,min(rst,eg[i].w));
if(!tmp) dep[y]=0;
eg[i].w-=tmp; eg[i^1].w+=tmp; rst-=tmp;
}
return flow-rst;
}
int dinic(){
int mxflow=0,flow;
while(bfs())
while(flow=dfs(s,inf)) mxflow+=flow;
return mxflow;
}
首先一遍 dp 求出 \(f_i\) 表示以第 \(i\) 个数结尾的最长不降子序列的长度。
容易发现，最终若取出 \(i\)，则 \(i\) 一定在子序列的第 \(f_i\) 个，考虑每个点 \(i\) 向 \(f_j=f_i+1\) 的 \(j\) 连边。为了保证每个点只选一次，拆点，入点出点间流量为 \(1\)。
第三问不限制 \(1\) 和 \(n\) 经过的次数，因此它们入点出点间的流量设为 \(\infty\)。
容易想到太空站为点，太空船为边。但是直接连难以刻画时间和周期。
考虑每个时刻对每个太空站新建结点，上一个时刻的太空站向下一个时刻的下一站连流量为太空船容量的边。枚举时刻跑最大流，直到地球到月球的流量 \(\geq\) 人数。
最小割
最大流 = 最小割
经典拆点转化。
考虑转化为最小割模型，由于最小割要求割边，而本题是割点，考虑将点转化为边，也就是将点拆为入点和出点，所有入点向出点连边，所有的边 \((x,y)\) 从 \(x\) 的出点连向 \(y\) 的入点，注意是双向边，然后求从 \(c1\) 的出点到 \(c2\) 的入点的最小割。
考虑 \(n\) 个点表示小朋友。若小朋友睡觉则连源点，不睡觉则连汇点。
现在要求矛盾会让源点汇点连通。对于有朋友关系的小朋友之间连边，显然若小朋友意见不同就会让源汇连通，此时可以发生冲突（割掉小朋友之间的边）或一个小朋友改变选择（割掉他和源/汇）的连边。
注意小朋友之间的连边要连双向边，因为可能是 \(A\) 让 \(B\) 和它一样选源点或是反过来，且这两种方案是不同的。可以发现双向边只会被割一条。
实际上是弱化版的集合划分模型。
集合划分模型
形如有一些物品，将其划分到 \(A,B\) 两个集合，其中物品 \(i\) 划分到 \(A,B\) 集合分别有 \(a_i,b_i\) 的代价，且由若干限制表示 \(i,j\) 划分至不同集合有 \(c_k\) 的代价。
考虑类似 P2057，将源点连每个点流量 \(a_i\) 表示划分到 \(B\) 集合，每个点连汇点 \(b_i\) 表示划分到 \(A\) 集合，有限制的点连双向边表示若有冲突必须割掉边，花费代价。
比较显然但不完全显然的集合划分模型。
首先不考虑“喜欢”关系，就是一个裸的集合划分。源点连 \(i\) 流量 \(d_i\) 保留表示愿意，连汇点 \(c_i\) 保留表示不愿意。
下面考虑刻画“喜欢”关系。发现难点在于确定每组是否合作。仅凭借选择是否愿意并不能推出是否合作，考虑对每组新建一个点表示是否合作。钦定若这个点连了源点，就表示合作，连汇点表示不合作。由于两个人中有一个人不愿意就必须不合作，所以若合作点与源点相连，且组内有人不愿意，就要不合法源汇连通，所以合作点向组内成员连流量 \(\infty\) 的边（表示强制限制，不能割断）。
然后处理关系就容易了。第一种情况 \(A\) 合作失败（合作点与汇点相连），且 \(B\) 选择愿意（与源点连），就 \(B\) 向 \(A\) 的组合作点连 \(a_i\) 的边，第二种情况 \(A\) 拒绝（连汇点），\(B\) 合作成功（合作点与源点连），就从 \(B\) 的合作点向 \(A\) 连 \(b_i\) 的边。
注意有的时候合作点和源点或汇点并没有任何间接相连的边，这时候代表决定其合作或不合作不需要代价，不会对答案产生影响（当时因为这个问题想了好久）。
感觉比上面那题好想一点。选文/理为两个集合，这题最小割模型其实是保留的边最大，所以边的流量和保留它表示的实际选的科目是一致的（下面默认源点为文，汇点为理）。
同样难以表示考虑新建节点，对于每个点周围全选文/理新建节点，只要有一个人选了相反的理/文，边就要割掉不能计入答案，容易想到全选文的点连原点，再连他周围的点和他自己，全选理是对称的。
和上面那题一样，不多说了。
需要注意的是表示都选 \(A\) 和都选 \(B\) 的决策点不能合并，不然会导致形如 \(s\to i \to \text{决策点} \to j \to t\) 的奇怪的流。见这个帖子。
以及注意边会达到 \(10^6\) 级别，数组不能开小。
最大权闭合子图
形如一个有向图，点有点权，选若干点，选了某个点必须选它的所有出点，要求选出的点权和最大（存在负点权，不然直接全选了）。
考虑集合划分模型，将点划分为“选”和“不选两个集合”。规定与源点相连表示选，与汇点相连表示不选，所以源点连 \(i\) 流量为 \(0\)，\(i\) 连汇点流量为 \(w_i\)。
闭合子图的要求形如“选了 \(u\) 必须选 \(v\)”，由于要求最大割，所以 \(u\to v\) 连边 \(-\infty\)，表示不能割的强制限制。
图连完之后要求最大割，但是最大割是 NP-hard 问题， 考虑权值取反求最小割。这时候出现了一些负权边，有负权的流是不好处理的，考虑对 \(w_i<0\) 的点 \(S\to i\) 和 \(i \to T\) 的边同时加上 \(w_i\) 的权值，然后再减去 \(\sum_{w_i>0} w_i\)（因为这两条边都割掉一定不优，都不割一定不行，所以一定会保留恰好一条边，也就是让答案增加 \(w_i\)），再取反。
其实上面的操作相当于先强制选了所有正权点，然后和源点连边，割掉表示不选，负权点和汇点连，割掉表示选，也就是 割=不选的正权点+选的负权点的绝对值=不选的正权点-选的负权点，那么 割-正权点和=-（选的正权点+选的负权点）=-答案，所以 答案=正权点的和-割。
很一眼吧。
也挺一眼的。
但是这题的区别是选择有先后顺序，也就是出现环就没有合法的选择方案，因此环和能到达环的点都不能选。拓扑排序预处理一下把这些点 ban 掉就行了。
较为复杂的最大权闭合子图，但并不难。
首先对于 \(d\) 数组，显然 \(d_{l,r}\) 选了 \(d_{l,r-1},d_{l+1,r}\) 必须要选。接下来考虑费用，对于 \(mx^2+cx\)，分开计算。\(cx\) 和吃过的某种寿司个数有关，考虑直接将其计入 \(d_{i,i}\)，对于 \(mx^2\) 只和是否吃过某种寿司有关，考虑对每种寿司建一个点，代价 \(mx^2\)，选了 \(d_{i,i}\) 就必须选 \(a_i\) 对应的点。至此已转化为模板。
还是 CF 的题比较有趣 qwq
首先看到 \(k\) 个子集的并集大小 \(\geq k\) 这个东西一下就想到了 Hall 定理，考虑二分图匹配。左部点表示集合，右部点表示集合中的元素。
题目保证了任意集合的集合都有完美匹配，也就是如果对原图求一个完美匹配，只保留匹配的边，任意合法的答案的匹配一定存在。
因此如果选了一个左部点 \(u\)，对于 \(u\to v\)，若 \(v\) 不是 \(u\) 的匹配点，那么 \(v\) 的匹配点也必须被选上。可以发现所有合法的集合都可以这样生成。
然后就转化为最小权闭合子图，权值取反跑最大权闭合子图即可。
最小费用最大流
最小费用最大流 EK 板子：
bool spfa(){
memset(dis,0x3f,sizeof(int)*(n+1));
memset(inq,0,sizeof(int)*(n+1));
q.push(s),inq[s]=1;
flow[s]=inf,dis[s]=0; lst[t]=0;
while(q.size()){
int x=q.front(); q.pop(),inq[x]=0;
for(int i=hd[x];i;i=eg[i].nxt){
int y=eg[i].v;
if(!eg[i].f) continue;
if(dis[x]+eg[i].c<dis[y]){
dis[y]=dis[x]+eg[i].c;
lst[y]=i; flow[y]=min(flow[x],eg[i].f);
if(!inq[y]){
q.push(y); inq[y]=1;
}
}
}
}
return lst[t]!=0;
}
void EK(){
mxflow=0,mncst=0;
while(spfa()){
mxflow+=flow[t];
mncst+=flow[t]*dis[t];
int nw=t;
while(nw!=s){
eg[lst[nw]].f-=flow[t];
eg[lst[nw]^1].f+=flow[t];
nw=eg[lst[nw]^1].v;
}
}
}
费用流，限制在点上所以拆点。
由于取出数之后就变成 0，可以看成每个点能被经过无数次，第一次经过收益是 \(a_{i,j}\)，之后都是 0。每个点拆成入点和出点，入点向出点连一条流量 1，费用 \(a_{i,j}\) 和一条流量 \(\infty\)，费用 0 的边。可以向下和向右走，所以每个点的出点向它的右下两点的入点连 \((inf,0)\) 边。最后源点向入点，出点向汇点连边。
最多走 \(k\) 次，所以再建一个新汇点，原汇点向新汇点连流量为 \(k\) 的边。
无源汇上下界可行流
这是很多东西的的基础。
对于每条边考虑把下界流满，然后每条边的流量限制改为上界减下界。但是这个时候可能有一些点不满足流量平衡，此时新建超级源汇，将源点向流进大于流出的点连边，同理流进小于流出的向汇点连边来补齐流量。
此时流的大小为汇点连向源点的边流量。
有源汇上下界最大流
对于有源汇上下界可行流，流入源点和流出汇点的流量显然相等，所以汇点向源点连一条流量为 \(\infty\) 的边转化为无源汇上下界可行流。
而有源汇上下界最大流，就是先跑有源汇上下界可行流，记可行流为 \(flow1\)，即为汇点连向源点的边的流量，然后断掉原图汇点连向源点的边和超源超汇连的所有边，从原图的源点再跑最大流 \(flow2\)，最后的答案就是 \(flow1+flow2\)。
有源汇上下界最小流，则 \(flow2\) 为原图的汇点向源点的最大流，答案为 \(flow1-flow2\)。
做法正确性基于：对于任意一组可行流，在上面运行最大流算法总能获得最大流。原因是最大流算法是可撤销的。
有源汇上下界最大流模板。
有负圈的费用流
有负圈的费用流，不好跑 SPFA。
考虑把所有费用为负的边强制流满，费用变为原来的相反数。强制流满可以通过有源汇上下界网络流的方法解决，即汇点连源点并新建虚拟源汇。
网络流里面混一点二分图
最大匹配 = 最小点覆盖 （最大流 = 最小割）
最大独立集 = 点数 - 最小点覆盖
最大独立集 = 点数 - 最小点覆盖 秒了。
每个小行星相当于规定行和列至少选一个。最小点覆盖模型。
由 最小点覆盖 = 最匹配，秒了。当然想写网络流也可以。
很久之前做过的题，大概是看到上面那题所以想起来了。和上面一题几乎一样，只是要输出答案。
注意到一个白点必须被涂上，并且只有两种方式，以其上方最近的黑点，或以其左方最近的黑点。
每个黑点有两种身份：向右涂或向下涂，对于每个黑点建两个点，向右涂在左边，向下在右边，形成二分图。对于白点，左边最近向上方最近连边表示两个至少选一个，于是就是一个最小点覆盖（最小割）问题，跑匈牙利或 Dinic 即可。
标签：int,eg,源点,网络,汇点,最小,流量,相关 From： https://www.cnblogs.com/wonderfish/p/18683391