基础知识形式化定义：二分图：\(G=(L,R,E)\)，满足\(\forall(u,v)\inE\)都有\(u\inL,v\inR\)或\(u\inR,v\inL\)。可知“图中没有长度为奇数的环”是这个图是二分图的充分必要条件。图的匹配是一个\(E_m\subseteqE\)满足\(\nexistsi\inV(\text{当}G

EK（转）dinic（转）EK（未完）以此份代码为例//P3376【模板】网络最大流//EK算法#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;constintN=410,M=10010;intn,m,S,T,h[N],e[M],w[M],ne[M],idx,pre[N],dist[N],st[N],ans,g[N][N];voidadd(inta,intb,in

以下考虑完备匹配的必须边（非完备匹配要用到网络流）给定一张二分图，其最大匹配方案不一定是唯一的。若任何一个最大匹配方案的匹配边都包括\((x,y)\)，则称\((x,y)\)为二分图匹配的必须边以下证明假设我们已经求出了一个最大匹配在完备匹配时，一条边\((x,y)\)是必须边，当且仅当满足以

反转左右翻转、上下翻转（不总是可行）切割从图像中切割一块，然后变形到固定的形状切割的方法：随机高宽比、随机大小（[8%,100%]是占原始图片的多少）、随机位置颜色改变色调、饱和度、明亮度(eg[0.5,1.5],在当前值得基础上作用，当前值是1.0)数据增广通过变形数据来获取多样性从而使

最大流对于网络\(G=(V,E)\)，给每条边指定流量，得到合适的流\(f\)，使得\(f\)的流量尽可能大。此时我们称\(f\)是\(G\)的最大流。Dinic算法思想考虑在增广前先对\(G_f\)做BFS分层，即根据结点\(u\)到源点\(s\)的距离\(d(u)\)把结点分成若干层。令经过\(u\)

二分图定义：一张图的\(N\)个节点可以分为\(A,B\)两个非空集合，满足同一个集合中的任意两个点没有连边。集合\(A,B\)分别叫做二分图的左部和右部，如图所示：二分图的判定交替染色，只有相邻的点颜色不一样时才可能是二分图，定理：二分图一定不存在奇环（易证）。判定：搜索\(dfs\)或

考虑\(EK\)算法求解最大流。每次找一条最小剩余流量\(d>0\)的\(s\rightsquigarrowt\)的路径。然后对之流下\(d\)的水。这个操作我们称之为增广，所找到的这条路径叫做增广路。一直增广到不存在任何增广路为止。发现这样的贪心策略有时是错误的。考虑反悔。连一条反边，反

1网络流相关概念网络流的概念分为网络和流。网络是指一种特殊的有向图\(G=(V,E)\)，有容量和源汇点\(s,t\)。对于一个网络，流需要满足以下性质：每条边上的流量不能大于它的容量。每个点流入的流量等于流出的流量。而对于整个网络和它上面的流，定义流的流量为源点流出的流量

1.网络最大流1.1容量网络和网络最大流 1.1.1容量网络设G(V,E)是一个有向网络，在V中指定了一个顶点，称为源点（记为Vs），以及另一个顶点，称为汇点（记为Vt）；对于每一条弧<u,v>∈E，对应有一个权值c(u,v)＞0，称为弧的容量（capacity）。通常把这样的有向网络G称为容量网络。 1.1.2弧

网络最大流Dinic算法代码笔记代码思路主体部分：构造分层图，找增广路（即bfs和dfs）辅助部分：当前弧优化（在bfs中进行重置，在dfs中进行更新）整合：首先是存图与主函数部分，通常还包括对问题的转换（也就是建图）。剩下的就是bfs和dfs。考虑bfs需要实现哪些功能：最主要地，它需要提供一个分

多模态是近年来深度学习圈子里的热点话题，最近的sora、去年的sam等。究竟何为多模态？而多模态中又有哪些难题呢？（可参考https://zhuanlan.zhihu.com/p/582762843?utm_id=0）多模态应当指多种异构数据协同参与，实现任务目的。多模态主要研究：1.特征对齐2.特征交互3.特征共性。特征对齐

传送门题意：有\(n\)个队友和\(m\)个敌人，每个队友\(i\)有\(a_i\)颗子弹。敌人\(j\)有\(b_j\)颗子弹。队友击杀敌人，必须\(a_i>b_j\)，然后会获得\(a_i-b_j+w_j\)的收益。（\(w_j\):每个敌人都有一个参数）每个队友只能打一个敌人，可以不打。求最大收益。【费用流模型

一文带你搞懂匈牙利算法附赠自动驾驶学习资料和量产经验：链接什么是匈牙利算法最近在研究一个比较有意思的应用—车辆追踪算法。传统的车辆追踪算法是基于检测器检出车辆，之后使用卡尔曼滤波和匈牙利算法来进行位置预测与数据级联的。关于卡尔曼滤波，我之前已经写过一篇文章进行

传送门题意：已知未来\(n\)天的股价\(c_i\)，每天可以买入一支或者卖出一支，求\(n\)天后利润总额最大是多少。算法：模拟费用流。【费用流模型】把每一天抽象为一个结点：\(d_1\simd_n\)。\(S\rightarrowd_1\simd_n\)，容量\(1\)费用\(-c_i\)。\(d_1\simd_n\rightarrowT

P1484种树有\(n\)个坑。第\(i\)个坑种树的价值是\(c_i\)，相邻坑不能同时种。可以种\(k\)颗树，求最大价值。模拟费用流，建图类似这样：中间两层结点之间有\(7\)条边，表示\(n=7\)的情况。相邻两条边，例如\(1,2\)总流入量为\(1\)，\(2,3\)总流出量为\(1\)，也不可能出现相

模拟费用流。传送门题意：共\(n=x+y+z\)个人，每个人可以选择获得\(a_i\)个金币或\(b_i\)个银币或\(c_i\)个铜币。要选\(x\)个人拿金币，\(y\)个人拿银币，\(z\)个人拿铜币。问币数总和最大是多少。\(n\le10^5\)。先建出费用流模型：把一个人的选择视作一个人流到了金币/

Decribe:给定\(n\)个点\(m\)条边，每条边有一个流量\(f\)。给定起点\(s\)和终点\(t\)，求最大流。（\(n\le1200,m\le120000\)）Solution:当\(n,m\)来到这样一个上界，Dinic稍稍被卡就过不去了，与其研究奇奇怪怪的Dinic优化，真不如学一个HLPP，它又不难。（又不会吃掉你）学

零、基本概念直接走OIwiki或者看蓝书吧。一、Ford-Fulkerson增广“该方法运用贪心的思想，通过寻找增广路来更新并求解最大流。”主要流程就是每次选一些增广路，以来更新最大流。但这个贪心思路不一定能保证正确性。Ford-Fulkerson增广的核心技术是通过设置反向边来实现反

更好阅读体验CHAPTER0废话1.常见的最大流算法可以大致分为两种：找增广路和预流推进2.从理论时间复杂度上界来看，找增广路算法的最坏时间复杂度为\(O(n^2m)\)，而预流推进算法的最坏时间复杂度为\(O(n^2\sqrt{m})\)，看起来预流推进要显然优于找增广路，但在实际应用（尤指OI）中，由于包

网络流前言当听到网络流量之后感觉是在充话费网络流(network-flows)是一种类比水流的解决问题方法，与线性规划密切相关。它模拟了水流从起点经过复杂的网络流向终点的过程就像自来水厂的水经过无数根水管子流到了家里而最大流就是最多有多少水流到了家里算法流程EK

这道题目求的是最小的代价，我们每选择某一行/列就会产生代价，故将行/列作为二分图的节点，然后就可以知道求的是最小点覆盖这里我还要写一下konig定理的另一种证明首先证明合法性。在求出最大匹配后，我们从每条匹配边任选一个点组成一个点集\(S\)（注意根据定义，不同匹配边的两个端点是

当学习笔记用，持续更新。写给自己看的，图有点少。如果有人真想通过这篇博客学网络流的话也不是不行……因为更新极慢无比，所以这篇博客里的各份代码码风可能会出现巨大的差别。关于学习途径显然有无数人在自学网络流的时候因为网上大部分题解的姿势都过于抽象而被劝退，所以提一下

网络流与二分图初步我们约定，对于有向图\(G=(V,E)\)，分析复杂度时\(m=|E|,n=|V|\)。在分析时间复杂度时，网络流的实际表现基本都优于其理论上的时间复杂度表现。I概念（1）网络流：在一个有向带权图上（不考虑自环和重边），与最短路类似，我们定义一个源点\(s\)和一个汇点\(t\)

最大流问题有向图G中，有两个特殊的点，源点和汇点，每条边有指定的容量，求S到T的最大流。就像从源点放水，水量无穷大，汇点的水量是多少？定义c为容量，f为流量流量守恒\(f(x,y)\leqc(x,y)\)容量性质\(\sumf(u,x)=\sumf(x,u)\)斜对称性\(f(x,y)=-f(y,x)\)容量网络，流量网络

【概念】都是无向图的概念支配集：一个点集，使得无向图中每个点要么是点集中的点，要么与点集相邻。独立集：一个点集，使得点集中任意两点不相邻。以上两个在任意图中都是NP问题，也就是无法在多项式时间内求解的问题。点覆盖：一个点集，使得所有边都至少与点集中一个点相连。