知识点总结
网络流,说白了就是把有向带边权的边看成一条水管，权值就是这个水管的最大流量，源点出水，汇点入水，其余的普通点（水管节点）出入水都得平衡。
最大流问题：整个系统最大的流量
不管是EK还是dinic 精髓都是建反边
反边类似于反悔贪心，在用了一个水管的流量的同时把权值加回到他的反边上，反边参与算法过程，这样，在我们想再次使用一个边的时候，就直接用反边完成了反悔。
注意反边不等于双向边，双边可以是对每一个方向边见了一组正反边，也可以变成一组正反边，权值各自付成w，效果似乎是等价的（存疑）
别的都还挺好理解的，建边暂时背代码就可以了
贴个板子
struct edge{
int to,nxt,val;
}e[2*N*N];
void add(int u,int v,int w){
e[++tot].to=v;
e[tot].nxt=head[u];
e[tot].val=w;
head[u]=tot;
e[++tot].to=u;
e[tot].nxt=head[v];
e[tot].val=0;
head[v]=tot;
}
bool bfs(){
queue<int> q;
for(int i=1;i<=n+2;i++) dis[i]=INF;
q.push(s);
dis[s]=0;
now[s]=head[s];
while(!q.empty()){
int u=q.front();
q.pop();
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
if(e[i].val>0&&dis[v]==INF){
q.push(v);
now[v]=head[v];
dis[v]=dis[u]+1;
if(v==t) return 1;
}
}
}
return 0;
}
int dfs(int u,int w){
if(u==t) return w;
int k,res=0;
for(int i=now[u];i&&w;i=e[i].nxt){
now[u]=i;
int v=e[i].to;
if(e[i].val>0&&(dis[v]==dis[u]+1)){
k=dfs(v,min(w,e[i].val));
if(k==0) dis[v]=INF;
e[i].val-=k;
e[i^1].val+=k;
res+=k;
w-=k;
}
}
return res;
}
int dinic(){
int ans=0;
while(bfs()){
ans+=dfs(s,INF);
}
return ans;
}
最小割问题 可以形象理解为把图分成两个部分，两部分之间的边直接切开，切的边权就是割的容量，最小割就是最小割容量
通过感性理解可得 最大流=最小割
结论直接用
最大流最小割问题关键在于建模，没有什么固定套路，考点一般就在这里
有些小技巧：
1.$INF$的边权代表随便流（割不开）
2.分层思想 其实是一种考虑图上点的方式 把各个点按某种形式分属不同层，考虑问题的时候可以从层出发和分层图最短路区分，听老师讲的时候就是这里蒙了
P4897很有意义的一道题，当多次查询$f(s,t)$ 时，暴力时间复杂度必炸
采用分治思想，对于每一部分图，在全局跑最小割，利用 $dis$ 数组就可以区分割出的两个部分，把这两部分连一条边权为最小割的边（不是在原图上）就可以构成一颗重构树，两点源汇最小割可以转化为两点间距离
也可以一边跑一边记录答案，可以倍增查询但没必要，数据范围往往允许用一些暴力一点的手段，这个时候没必要在冗长的代码后面加不稳定因素
还有推流，正反边总量不变，直接倒回原状态就行
费用流
不难理解 就是把bfs序找边换成了spfa找最短路 回头更新板子
循环流 没有源点和汇点，所有点都要保证平衡，定义上下界 还没做到题，回头更新
小优化 把边按照$2^t$分层再跑，很玄学但是有用
见课堂笔记
未理解内容
CS算法完全没懂，不过好像几乎完全不考，暂时费用流有对应的算法可以应对
反边的原理还是只能感性理解
消圈懂了但是也是感性理解
jhonson算法原来就是背结论，现在还是背结论
做题总结
vjudge 5/14
1.板子不熟练，每道题从头打模板部分都没一遍过，消耗了不少调试时间
2.建模思想不掌握，不知道咋连边，就是题的主要考点应对不了
3.调代码有时候会不在状态，一点小错找一年，比赛有时候也有这个问题，估计跟效率和算法理解都有关系，其实最慢的反倒是第一道做的题，所以说算法理解还是关键
4.题的难度压力一下大了，模拟赛感觉要寄，以拿部分分为主，冲正解不要轴，先考虑下可行性，想错了同时浪费思考时间和打代码时间
标签：师大附中,return,val,int,head,tot,20231210,D1,dis From： https://www.cnblogs.com/youlv/p/18076964/daily_2023ssdfzD1_1