网络流

网络流学习笔记

注意要点：

$1.$费用流

用$SPFA$，记住不要v==t就return 1，松弛完毕后再判断。

运行$Dinic$的时候，记住要打$vis_i$标记，离开节点$u$，遍历出边应清空$vis$，判断$vis$。

加上ret+=k*edge[i].c，判断的时候记住d[v]==d[u]+edge[i].w，for循环记得判断f>0，然后记得建双向边（一个容量变为$0$，一个费用变成了原来的相反数）

$2.$牢记点：

$a.$网络流一般对模板没有考察，考察在于建图，对图建模上。牢记网络流思维模型，认真思考，切记不要改动板子（除非像是记录pre等前驱点）

$b.$做题中心在于费用流上，思考区别

模板

最大流

$Dinic$算法

inline int BFS()//BFS最短路增广
{
	queue <int> q;	
	memset(d,0x3f,sizeof(d));
	memcpy(cur,head,sizeof(head));
	q.push(s);d[s]=0;
	while (!q.empty())
	{
		int u=q.front();q.pop();
		for (int i=head[u];i;i=edge[i].next)
		{
			int v=edge[i].v;
			if (d[v]==INF && edge[i].w)
			{
				q.push(v);
				d[v]=d[u]+1;//对图进行分层
				if (v==t) return 1;
			}
		}
	}
	return 0;
}
inline int Dinic(int u,int f)
{
	if (u==t) return f;
	int k,res=0;
	for (int i=cur[u];i && f;i=edge[i].next)//剪枝
	{
		int v=edge[i].v;cur[u]=i;//当前弧优化
		if (d[v]==d[u]+1 && edge[i].w)
		{
			k=Dinic(v,min(edge[i].w,f));
			if (!k) {d[v]=INF;continue;}//剪枝
			edge[i].w-=k,edge[i^1].w+=k;//调整边权
			f-=k,res+=k;//流量
		}
	}
	return res;
}

$Dinic$算法在$EK$算法上改进而来，通过对图分层，求最短路来进行增广，最多会增广$n$次，单次最劣复杂度为$\Theta(nm)$，总时间复杂度$\Theta(n^2m)$

背个板子就可以了

最小割

$1.$全局

咕咕咕

$1.$ $s->t$最小割

根据最大流最小割定理，最大流=最小割

所以套一次$Dinic$求出来就可以力

费用流

$SSP$

不会，咕咕咕

只会用$SPFA+Dinic$的$SSP$捏qwq

实际上只用把$bfs$改成$SPFA$，加个vis数组就可以力，而且vis可以$Dinic$和$SPFA$通用，好耶！

注意点:

$a.$注意$SPFA$全部松弛完后（不是v==t）才return

$b.$ $Dinic$进入点$u$离开点$u$注意打上标记&取消标记

$c.$判断能不能继续递归的时候也要判断点没在递归栈内(!vis[v])

$SPFA$实现的$SSP$

inline int SPFA()
{
	queue <int> q;
	memset(d,0x3f,sizeof(d));
	memcpy(cur,head,sizeof(head));
	q.push(s),d[s]=0;
	while (!q.empty())
	{
		int u=q.front();q.pop();
		vis[u]=0;
		for (int i=head[u];i;i=edge[i].next)
		{
			int v=edge[i].v;
			if (d[v]>d[u]+edge[i].c && edge[i].w)
			{
				d[v]=d[u]+edge[i].c;
				if (!vis[v])
				{
					q.push(v);
					vis[v]=1;
				}
			}
		}
	}
	return d[t]==INF?0:1;
}
inline int Dinic(int u,int f)
{
	if (u==t) return f;
	vis[u]=1;int k,res=0;
	for (int i=cur[u];i && f;i=edge[i].next)
	{
		int v=edge[i].v;cur[u]=i;
		if (edge[i].w && d[v]==d[u]+edge[i].c && !vis[v])
		{
			k=Dinic(v,min(f,edge[i].w));
			if (k)
			{
				edge[i].w-=k;
				edge[i^1].w+=k;
				res+=k,f-=k;
				ret+=k*edge[i].c;
			}
			else d[v]=INF;
		}
	}
	vis[u]=0;
	return res;
}

$Primal-Dual$

和$Johnson$一样换个元跑$dijkstra$就行了，不过没写过/kk

经典例题：网络流24题

常见建模：

$1.$二分图的最大独立集

例题：骑士共存问题，长脖子鹿，方格取数

通过黑白拆点，奇偶性划分，建出$s->0->1->t$的模型

常用：棋盘类

$2.$拆为入点，出点

例题：逃跑，蜥蜴

通过拆点，将图上的点权考虑转化为边权，并通过出点入点实现某些性质

常用：点权转边权类

$3.$将不同物品分开罗列，互相连边

类似于黑白染色，但是可能有多种物品$(\geq2)$，考虑分开罗列，按照题目所给条件飞开连权值为$w$（如只能用一次等条件时，$w=1$）的边

例题：酒店之王，教辅的组成

$4.$费用流

看似最大流，实际费用流

注意细节

例题：任务分配

$5.$向同种物品连边

体现类似“流动性”，转移，向同类连边

例题：猪

$6.$记录前后驱

用pre数组或检查边权为$0$的边

例题：圆桌问题，飞行员配对方案

$7.$最小割

最大流=最小割

$Dinic$求出最小割即可

注意$CF103E$ $Buying Sets$这题比较神，用$Lim-w$记录边权，$ans$设置为一个极大的数，最后减去$Dinic$的答案，值得思考。

例题：奶牛的电信，$CF103E$ $Buying Sets$

后记

关于上下界的学习笔记：

咕咕咕喵喵喵