基础网络流做题方法简单归纳与整理
Take_A_Single_6 · · 算法·理论
做网络流的一个重要的思路就是不管三七二十一先建模，然后把一些决策丢给网络流来思考。
推荐题单：【小峰の题单】网络流经典题目
推荐模板总结：【实时更新】提高-省选级模板汇总
粘一点代码凑长度
最大流最小割：
bool bfs()
{
for(int i=1;i<=n;i++)dis[i]=inf;//注意初始化是否完全，这里的 n 可以写为 t
while(q.size())q.pop();
q.push(s),dis[s]=0,now[s]=head[s];
int u;
while(q.size())
{
u=q.front(),q.pop();
for(int i=head[u];i;i=e[i].nxt)
{
int v=e[i].to;
if(e[i].val&&dis[v]==inf)
{
dis[v]=dis[u]+1,now[v]=head[v],q.push(v);
if(v==t)return 1;
}
}
}
return 0;
}
int dfs(int u,int flow)
{
if(u==t)return flow;
int t,res=0;
for(int i=now[u];i&&flow;i=e[i].nxt)
{
int v=e[i].to;
now[u]=i;//当前弧优化
if(e[i].val&&dis[v]==dis[u]+1)
{
t=dfs(v,min(e[i].val,flow));
if(!t)dis[v]=inf;
e[i].val-=t,e[i^1].val+=t,res+=t,flow-=t;
}
}
return res;
}//真的 dinic费用流：
bool spfa()
{
for(int i=1;i<=n;i++)dis[i]=inf,vis[i]=0;
memcpy(now,head,sizeof head);
while(q.size())q.pop();
q.push(s),dis[s]=0,vis[s]=1;
int u;
while(q.size())
{
u=q.front(),q.pop(),vis[u]=0;
for(int i=head[u];i;i=e[i].nxt)
{
int v=e[i].to;
if(e[i].val&&dis[v]>dis[u]+e[i].cost)
{
dis[v]=dis[u]+e[i].cost;
if(!vis[v])q.push(v),vis[v]=1;
}
}
}
return dis[t]!=inf;
}//spfa 建分层图
int dfs(int u,int flow)
{
if(u==t)return flow;
vis[u]=1;
int x,res=0;
for(int &i=now[u];i&&res<flow;i=e[i].nxt)
{
int v=e[i].to;
if(!vis[v]&&e[i].val&&dis[v]==dis[u]+e[i].cost)
{
x=dfs(v,min(e[i].val,flow-res));
if(x)e[i].val-=x,e[i^1].val+=x,res+=x,cst+=x*e[i].cost;
}
}
vis[u]=0;
return res;
}//这里用的是正规的 dinic，模板题题解几乎全是 EK一，最大流建模，考虑流量意义
- 主主树 每个人拆成打人的和被打的，直接通过矛盾关系建图即可
- 最小路径覆盖问题 每个点看做一条链，拆成起点
x 和终点x ，流量的意义为合并链，最后再残余流量上建并查集输出方案 - 教辅的组成 匹配类问题，根据匹配关系连边
二，最小割建模，考虑如何选边
- [ZJOI2009] 狼和羊的故事 最小割只割
s \to t ，所以不用考虑反向边的影响 - 方格取数问题 四联通矛盾考虑通过黑白二分图染色来表达
- [ARC176E] Max Vector 取值可以转化为割边，常规做法(dp，贪心)不好做考虑抽象思维上升到图论
三，费用流建模，设计流量表达合法性，费用表达最优解
- 负载平衡问题 搬一次的费用为
1 表示搬运次数 - 餐巾计划问题 逆向思维，如果使用后可以回收，考虑在保证存在的情况下把使用后的物品当原料。
- [CQOI2012] 交换棋子 流量表达能否达到目标状态，费用表达交换次数，黑白可以只考虑一种
四，概括性做题方法总结
- 拆点，设计一个为起始点一个为终止点，通过设计中间的边来解决问题
- 寻找矛盾/关联，通过这样的关系建边
- 逆向思维，转化题意。这一点在其他算法中也颇为常见