dede网站站内推广方法,服装服饰东莞网站建设,我的家乡网页制作素材,网站建设设计开发公司注#xff1a;笔者是蒟蒻#xff0c;所以本文几乎是干货#xff0c;枯燥无味甚至可能会引人不适#xff0c;请读者谨慎阅读。
为了笔者快爆掉的肝点个赞好吗#xff1f;#xff1f;#xff1f;
Part.1 网络流基础定义
一个有向带权图 G ( V , E ) G(V,E) G(V,E) 是…注笔者是蒟蒻所以本文几乎是干货枯燥无味甚至可能会引人不适请读者谨慎阅读。
为了笔者快爆掉的肝点个赞好吗
Part.1 网络流基础定义
一个有向带权图 G ( V , E ) G(V,E) G(V,E) 是一个网络当且仅当
图中只有一个入度为 0 0 0 的点即源点 S S S图中只有一个出度为 0 0 0 的点即汇点 T T T每条边 u → v u\to v u→v 的权值为正数这个数表示此边的容量记作 c u , v c_{u,v} cu,v。
网络流可以具象为流水的系统源点就是水源能无限的供应水而汇点就是取水点无限的消耗水边就是管道而且通过水的数量不能超过其容量。
形式化的讲记在边 u → v u\to v u→v 之间的流量为 f u , v f_{u,v} fu,v。若边在原图中存在则会有如下性质 0 f u , v ≤ g u , v 0f_{u,v}\le g_{u,v} 0fu,v≤gu,v f u , v − f v , u f_{u,v}-f_{v,u} fu,v−fv,u对于一个点 u u u和所有 x → u x\to u x→u 的 x x x 以及 u → y u\to y u→y 的 y y y有 ∑ x f x , u ∑ y f u , y \sum\limits_{x} f_{x,u}\sum\limits_{y} f_{u,y} x∑fx,uy∑fu,y这个性质被称作流量守恒即流入多少水就流出多少水。
增广路定义为一条从 S S S 到 T T T 剩余容量大于 0 0 0 的路径。
残量网络定义为已经流过一些流量后删除满流的边的网络。
Part.2 最大流及其应用
模板题。
定义最大流为在满足上述性质的前提下流入汇点的流量总和的最大值。重点在于如何求这个值。
首先有一个贪心就是每次选择一个增广路流出路径上的剩余流量的最小值然后更新剩余流量。
上述算法显然是错误的那我们如何补救呢
考虑对于每个边建立反向边初始的容量为 0 0 0。每次增广时一条边容量减 x x x其反向边容量加 x x x。结合下图理解 可以发现建立反向边后相当于给了一次撤销的机会而上述假贪心加上这个优化过后就是对的了笔者并不会证明。这个算法就是 FF 算法时间复杂度与流量有关。
而每次选择源点到汇点的最短增广路进行增广就得到了 EK 算法时间复杂度 O ( n m 2 ) O(nm^2) O(nm2)。
每次只增广一条太亏了所以把所有最短路径一起增广。具体的以 S S S 为起点对图 BFS然后按距离分层就只需要考虑相邻层之间的边了。从 S S S 开始携带 ∞ \infty ∞ 的流量向下遍历每次枚举当前节点的邻居尽量将手里的流量送出去。
注意到有效边组成的图一定是个 DAG说明如果将一条边的剩余容量变成 0 0 0这条边就不会再访问了。所以可以开个数组 n o w u now_u nowu 表示 u u u 访问到那个邻居了DFS 的时候就从 n o w u now_u nowu 开始遍历后面的边。
这个小优化叫做当前弧优化加上这个优化的算法叫做 Dinic。其时间复杂度就降到了 O ( n 2 m ) O(n^2m) O(n2m)而且跑不满 n n n 开 1 0 4 10^4 104 m m m 开 1 0 5 10^5 105 都可以干过去特别的在二分图中Dinic 的时间复杂度为 O ( m n ) O(m\sqrt n) O(mn )。这是 OI 中最常用的最大流算法。
放一下板子的代码
#include bits/stdc.h
#define int long long
using namespace std;
const int N 2e25,M 5e35;
int n,m,s,t,cnt 1,head[N],to[M1],nxt[M1],g[M1];//cnt初始值为1方便获得反边
inline void add(int x,int y,int z)
{nxt[cnt] head[x];head[x] cnt;to[cnt] y,g[cnt] z;
}
int dis[N],now[N];
inline bool bfs()
{for(int i 1;in;i) dis[i] -1;queueint q;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 nxt[i]){int v to[i];if(g[i]0dis[v]-1){q.push(v);dis[v] dis[u]1,now[v] head[v];if(vt) return 1;}}}return 0;
}
int dfs(int u,int s)
{if(ut) return s;int k,res 0;for(int i now[u];i;i nxt[i]){if(!s) break; int v to[i];now[u] i;//当前弧优化 if(g[i]0dis[v]dis[u]1)//能流且位于下一层 {k dfs(v,min(s,g[i]));if(k0) dis[v] 2e9;g[i]-k,g[i^1]k,resk,s-k;} }return res;
}
signed main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cinnmst; for(int i 1,u,v,w;im;i)cinuvw,add(u,v,w),add(v,u,0);int ans 0;while(bfs()) ansdfs(s,2e9);coutans;return 0;
}最大流的用处太多了后文慢慢讲吧。
Part.3 费用流及其应用
模板题。
费用流其实就是在最大流上对于每个弧增加了一个属性费用每流过一个单位的流就会消耗对应的费用。让你求在流最大的情况下使得费用最少或最大。
先想想费用流中的反向边怎么建其实就是正向边的费用和反向边的费用成相反数就行了。
那怎么增广呢还记得最大流中的 EK 算法吗这个算法在求最大流是不是寻找的最短的增广路吗其实改到费用流里就每次把费用最少的增广路拿出来增广就行了这里是求最小费用最大流。然而由于图有负边权所以只能跑 SPFA。
时间复杂度是 O ( n m f ) O(nmf) O(nmf)其中 f f f 指最大流。这个很容易理解就是最多增广 f f f 次每次增广时瓶颈在于 SPFA所以是 O ( n m f ) O(nmf) O(nmf) 的。这个大大的跑不满由于在题目中建出来的图比较特殊最大流可能比较小 n n n 开 1 0 4 10^4 104 m m m 开 1 0 5 10^5 105 都可以干过去。这就是名言“最大流不卡 Dinic费用流不卡 EK”的由来。
放代码
#include bits/stdc.h
using namespace std;
const int N 5e35,M 1e55;
int n,m,s,t,cnt 1,head[N],now[N],nxt[M],to[M],g[M],fl[M];
inline void add(int x,int y,int w,int flow)
{nxt[cnt] head[x];head[x] cnt;to[cnt] y,g[cnt] w,fl[cnt] flow;nxt[cnt] head[y];head[y] cnt;to[cnt] x,g[cnt] -w,fl[cnt] 0;
}
int dis[N],mn[N];
bool vis[N];
inline bool spfa()
{for(int i 1;in;i)dis[i] 2e9,vis[i] 0;dis[s] 0,mn[s] 2e9,vis[s] 1;queueint q;q.push(s);while(!q.empty()){int u q.front();q.pop();vis[u] 0;for(int i head[u];i;i nxt[i]){int v to[i],w g[i];if(fl[i]dis[v]dis[u]w){now[v] i,dis[v] dis[u]w,mn[v] min(mn[u],fl[i]);if(!vis[v]) vis[v] 1,q.push(v);}}}if(dis[t]!2e9) return 1;return 0;
}
signed main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cinnmst;for(int i 1,u,v,w,flow;im;i)cinuvfloww,add(u,v,w,flow);int ans1 0,ans2 0;while(spfa()){ans1mn[t],ans2mn[t]*dis[t];int x t;while(x!s){fl[now[x]]-mn[t],fl[now[x]^1]mn[t];x to[now[x]^1];}}coutans1 ans2\n;return 0;
}至于最大费用最大流的求法你可以更改一下 SPFA 或者将费用取反写最小费用最大流都可以。
还是来几道例题吧可能比较多读者可以选择性阅读。
例题一P2045。
考虑将每个点 ( x , y ) (x,y) (x,y) 拆分为 i n x , y , o u t x , y in_{x,y},out_{x,y} inx,y,outx,y建立超级原点 S S S汇点为 o u t n , n out_{n,n} outn,n。连一条 S → i n 1 , 1 S\to in_{1,1} S→in1,1费用为 0 0 0容量为 k k k 的边表示最多走 k k k 次。对于一个点 ( x , y ) (x,y) (x,y)有如下几种边
一条 i n x , y → o u t x , y in_{x,y}\to out_{x,y} inx,y→outx,y费用为 a x , y a_{x,y} ax,y容量为 1 1 1 的边只能取一次表示将 ( x , y ) (x,y) (x,y) 中的数取出来一条 i n x , y → o u t x , y in_{x,y}\to out_{x,y} inx,y→outx,y费用为 0 0 0容量为 ∞ \infty ∞ 的边表示直接跳过 ( x , y ) (x,y) (x,y)一条 o u t x , y → i n x 1 , y out_{x,y}\to in_{x1,y} outx,y→inx1,y 或者 o u t x , y → i n x , y 1 out_{x,y}\to in_{x,y1} outx,y→inx,y1费用为 0 0 0容量为 ∞ \infty ∞ 的边表示往下或者往右走。
跑最大费用最大流即可。
例题二P3358。
首先发现一个开区间对其内部的点都有相同的覆盖次数贡献所以可以对区间的两个端点离散化。
首先可以想到将数轴上的点用费用为 0 0 0容量为 k k k 的边连成一条链如何刻画当前点的覆盖次数是现在的首要问题。
设流入当前点的流量为 f f f那么考虑构造一个网格使得 k − f k-f k−f 成为这个点的覆盖次数。明显对于线段 i i i连一条 l i → r i l_i\to r_i li→ri容量为 1 1 1费用为其长度的边可以符合条件。
建立超级源点和超级汇点跑最大费用最大流即可。
例题三CF277E。
发现一个点选父亲和这个点选儿子是互相独立的所以考虑拆点 i n x in_x inx 表示这个点去选儿子 o u t x out_x outx 表示这个点的父亲被选好了。
建立超级源点 S S S S S S 向每个 i n x in_x inx 连一条费用为 0 0 0容量为 2 2 2 的边表示最多选两个儿子。建立超级汇点 T T T每个 o u t x out_x outx 向 T T T 连一条费用为 0 0 0容量为 1 1 1 的边表示这个点的父亲选完了最多一个父亲。
如果两个点 x , y x,y x,y 满足 x x x 可以成为 y y y 的父亲连一条 i n x → o u t y in_x\to out_y inx→outy 容量为 1 1 1费用为两点距离的边这样最终的费用就是此树的权值。
跑最大费用最大流即可值得注意的是如果最终的最大流不是 n − 1 n-1 n−1就无解因为除了根节点之外每个点都得有父亲。
例题四CF863F。
首先可以暴力预处理出每个点的最终范围 l i ∼ r i l_i\sim r_i li∼ri显然如果 l i r i l_ir_i liri 无解否则必然有解。
注意到 x 2 1 3 ⋯ ( 2 x − 1 ) x^213\cdots(2x-1) x213⋯(2x−1)。将每种权值拆分为两个点 i n i in_i ini 和 o u t i out_i outi分别连上容量为 1 1 1费用为 1 , 3 , ⋯ , 2 n − 1 1,3,\cdots,2n-1 1,3,⋯,2n−1 的边如果有 k k k 个流量流入了 i n i in_i ini相当于有 k k k 个数的值为 i i i跑最小费用最大流最终的费用刚好是 k 2 k^2 k2符合题目所求。
最后的建图就十分显然了建立超级源点 S S S S S S 向每个 i i i 连容量为 1 1 1费用为 0 0 0 的边表示每个 a i a_i ai 只能选一个数每个 i i i 向 i n l i ∼ r i in_{l_i\sim r_i} inli∼ri 连容量为 1 1 1费用为 0 0 0 的边表示 a i a_i ai 可以选这个数。建立超级汇点 T T T每个 o u t i out_i outi 向 T T T 连容量为 ∞ \infty ∞费用为 0 0 0 的边。
然后跑最小费用最大流即可。
放一道不错的练习题P4249以及其双倍经验CF1264E。
Part.4 最小割及其应用
定义一张图的割为一种点的划分方式将图分为 s , t s,t s,t 两个集合其中 S ∈ s , T ∈ t S\in s,T\in t S∈s,T∈t。割的权值为 ∑ u ∈ s , v ∈ t c u , v \sum\limits_{u\in s,v\in t} c_{u,v} u∈s,v∈t∑cu,v。最小割就是权值最小的割。
最小割的几个性质
最小割和最大流是相等的即最大流最小割定理最小割的割边一定是满流边若删掉或减小某条满流边的容量后最大流不减小则该边一定不是最小割中的边网络流的任意一条增广路至少经过一条最小割边对于某满流边如果在残留网络中源点能到达该边一端点另一端点能到达汇点则该满流边就是关键割边即一定是最小割的一个割边。
例题一最大权闭合子图。 给出一张有向图 G ( V , E ) G(V,E) G(V,E)每个点有一个权值 w i w_i wi。现在要选出一个点集 V ′ V V′满足对于任意一条边 x → y x\to y x→y如果 x ∈ V ′ x\in V x∈V′则 y ∈ V ′ y\in V y∈V′。你需要让 ∑ x ∈ V ′ w x \sum\limits_{x\in V}w_x x∈V′∑wx 最大。 首先考虑最理想的情况即所有 w i 0 w_i0 wi0 的点都被选问题就变成了最小代价删掉正点权或加入负点权。所以考虑用最小割求解这是一种非常常见的套路。
设在一组割中与 S S S 相连的点就是选否则就是不选。对于 w i 0 w_i0 wi0 的点连边 S → i S\to i S→i容量为 w i w_i wi对于 w i 0 w_i0 wi0 的点连边 i → T i\to T i→T容量为 − w i -w_i −wi。
对于在原图中的一条边 x → y x\to y x→y连一条 x → y x\to y x→y容量为正无穷的边。这样就能保证如果 x x x 在集合 s s s 里 y y y 肯定在集合 s s s 里否则这组割的权值就会加上 ∞ \infty ∞肯定不是最小的。
跑出来的最大流就是最小的代价这样答案就能被轻松求出。
例题二P2057。
考虑用最小割求解在一组割中与 S S S 相连就是投赞成票否则就是投反对票。
首先如果 i i i 意愿赞成就与 S S S 连一条容量为 1 1 1 的边否则就向 T T T 连一条容量为 1 1 1 的边。这样如果这条边是割边就会因与自己意愿相反对割贡献 1 1 1 的权值。
对于一个朋友关系 ( x , y ) (x,y) (x,y)连两条 x → y , y → x x\to y,y\to x x→y,y→x 容量为 1 1 1 的边如果两个点不在同一集合内其中一条边会对割贡献 1 1 1 的权值。
跑最小割即可。
练习题P4313。
Part.5 上下界网络流及其应用
首先什么是上下界网络流就是每条边除了流出网络的上限 c u , v c_{u,v} cu,v即容量新增了一个性质下界 b u , v b_{u,v} bu,v要求 b u , v ≤ f u , v ≤ c u , v b_{u,v}\le f_{u,v}\le c_{u,v} bu,v≤fu,v≤cu,v。
首先是无源汇上下界可行流。
什么是无源汇相当于网络中的每个点都满足流量守恒。让你求出满足这些条件的一种流法。
首先先考虑去掉下界的限制即每条边先流出 b u , v b_{u,v} bu,v 的流量。但这样明显会不符合流量守恒考虑建一张图去调整。
设 i n u ∑ ( v , u ) ∈ E b v , u , o u t u ∑ ( u , v ) ∈ E b u , v in_u\sum\limits_{(v,u)\in E} b_{v,u},out_u\sum\limits_{(u,v)\in E} b_{u,v} inu(v,u)∈E∑bv,u,outu(u,v)∈E∑bu,v。如果 i n u o u t u in_uout_u inuoutu说明还需要流出 i n u − o u t u in_u-out_u inu−outu 的流量否则还需要流入 o u t u − i n u out_u-in_u outu−inu 的流量。
考虑建图求解对于 i n u o u t u in_uout_u inuoutu连一条 S → u S\to u S→u容量为 i n u − o u t u in_u-out_u inu−outu 的边如果 o u t u i n u out_uin_u outuinu 连一条 u → T u\to T u→T容量为 o u t u − i n u out_u-in_u outu−inu 的边。对于 ( u , v ) ∈ E (u,v)\in E (u,v)∈E连一条 u → v u\to v u→v容量为 c u , v − b u , v c_{u,v}-b_{u,v} cu,v−bu,v。对于这个图跑网络流最大流如果所有与 S S S 相连的边都是满流原图就有可行流实际流量为图中这条边的流量加上 b u , v b_{u,v} bu,v否则无解。
加上费用也很简单用 ∑ ( u , v ) ∈ E b u , v × w u , v \sum\limits_{(u,v)\in E} b_{u,v}\times w_{u,v} (u,v)∈E∑bu,v×wu,v 加上最小费用最大流即可。
那如何求有源汇上下界可行流/最大流/最小流呢
第一个直接转化为无源汇上下界可行流连一条 T → S T\to S T→S下界为 0 0 0上界为 ∞ \infty ∞ 即可。跑出一组可行流后此时的真实流量是 T → S T\to S T→S 的流量记为 f 1 f_1 f1。
那如何求最大流呢
考虑调整法。还记得求可行流时建的图吗其实我们只需要拆掉 T → S T\to S T→S 的边然后再跑一遍 S → T S\to T S→T 的最大流记为 f 2 f_2 f2。两者相加就行了。
同样的去求最小流发现跑 T → S T\to S T→S 的最大流相当于退流记为 f 2 f_2 f2两者相减就行了。
这里放一下求最大流的模板的代码
#include bits/stdc.h
#define int long long
using namespace std;
const int N 2e25,M 1e4N;
int n,m,s,t,ss,tt,a[N],cnt 1,head[N],to[M1],nxt[M1],g[M1];
inline void add(int x,int y,int z)
{nxt[cnt] head[x];head[x] cnt;to[cnt] y,g[cnt] z;nxt[cnt] head[y];head[y] cnt;to[cnt] x,g[cnt] 0;
}
int dis[N],now[N];
inline bool bfs()
{for(int i 0;in1;i) dis[i] -1;queueint q;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 nxt[i]){int v to[i];if(g[i]0dis[v]-1){q.push(v);dis[v] dis[u]1,now[v] head[v];if(vt) return 1;}}}return 0;
}
int dfs(int u,int s)
{if(ut) return s;int k,res 0;for(int i now[u];i;i nxt[i]){if(!s) break; int v to[i];now[u] i;if(g[i]0dis[v]dis[u]1){k dfs(v,min(s,g[i]));if(k0) dis[v] 2e9;g[i]-k,g[i^1]k,resk,s-k;} }return res;
}
inline int dinic()
{int res 0;while(bfs()) resdfs(s,2e18);return res;
}
signed main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cinnmsstt;s 0,t n1; for(int i 1,u,v,c,b;im;i){cinuvbc;add(u,v,c-b);a[u]-b,a[v]b;}int mx 0;for(int i 1;in;i)if(a[i]0) add(s,i,a[i]),mxa[i];else if(a[i]0) add(i,t,-a[i]);add(tt,ss,1e18);if(dinic()mx) return coutplease go home to sleep,0;mx g[cnt];g[cnt] g[cnt-1] 0;s ss,t tt;coutmxdinic();return 0;
}例题一P4843。
建立超级源点 S S S以及超级汇点 T T T。 S S S 向每个 i i i 建立下界为 0 0 0上界为 ∞ \infty ∞ 的边每个 i i i 向 T T T 连一条下界为 0 0 0上界为 ∞ \infty ∞ 的边。由于原图中的每条边 ( u , v ) (u,v) (u,v) 都得覆盖一次于是连一条 u → v u\to v u→v下界为 1 1 1上界为 ∞ \infty ∞ 的边。
跑有源汇上下界最小流即可。
例题二P5192。
对于每天和每个少女飞别建一个点建超级源点 S S S以及超级汇点 T T T。每个少女 x x x 向汇点连下界为 G x G_x Gx上界为 ∞ \infty ∞ 的边源点向第 x x x 天连一条下界为 0 0 0上界为 D x D_x Dx 的边。第 x x x 天向第 y y y 个拍照的少女 T x , y T_{x,y} Tx,y 连一条下界为 L x , y L_{x,y} Lx,y上界为 R x , y R_{x,y} Rx,y 的边。
跑有源汇上下界最大流即可。
Part.6 二分图
一张图是二分图当且仅当这张图可以分为两个不相交的点集 A , B A,B A,B即 A ∪ B V , A ∩ B ∅ A\cup BV,A\cap B\emptyset A∪BV,A∩B∅满足不存在 ( u , v ) ∈ E (u,v)\in E (u,v)∈E 使得 u ∈ A , v ∈ A u\in A,v\in A u∈A,v∈A 或者 u ∈ B , v ∈ B u\in B,v\in B u∈B,v∈B。
一个图是二分图的充分必要条件是这张图里面没有奇环。当然也可以用黑白染色来判断一个图是否是二分图。
二分图的边覆盖/匹配/点覆盖/独立集问题
对于一张图有如下定义
边覆盖 G G G 的一个边集 E ′ ⊆ E E\subseteq E E′⊆E 满足其是 G G G 的边覆盖当且仅当对于每个点 x ∈ V x\in V x∈V存在另一个点 y y y 使得 ( x , y ) ∈ E ′ (x,y)\in E (x,y)∈E′即每个点至少是 E ′ E E′ 中一条边的端点匹配 G G G 的一个边集 E ′ ⊆ E E\subseteq E E′⊆E 满足其是 G G G 的匹配当且仅当 E ′ E E′ 中任意两条边不存在共同点点覆盖 G G G 的一个点集 V ′ ⊆ V V\subseteq V V′⊆V 是 G G G 的点覆盖当且仅当对于图中每条边其端点至少有一个属于 V ′ V V′独立集 G G G 的一个点集 V ′ ⊆ V V\subseteq V V′⊆V 是 G G G 的点覆盖当且仅当对于图中每条边其端点至多有一个属于 V ′ V V′
事实上对于任意一张图 G ( V , E ) G(V,E) G(V,E)有
如果 G G G 存在边覆盖则最小边覆盖加上最大匹配等于 ∣ V ∣ |V| ∣V∣。 证明首先构造出一个最大匹配 E ′ E E′记其端点组成的集合大小为 c c c明显 c 2 ∣ E ′ ∣ c2|E| c2∣E′∣现在考虑加边是其变为最小边覆盖而每加一条边 c c c 会加一最后我们需要将 c c c 变为 ∣ V ∣ |V| ∣V∣所以加边个数为 ∣ V ∣ − 2 ∣ E ′ ∣ |V|-2|E| ∣V∣−2∣E′∣最小边覆盖为 ∣ V ∣ − 2 ∣ E ′ ∣ ∣ E ′ ∣ ∣ V ∣ − ∣ E ′ ∣ |V|-2|E||E||V|-|E| ∣V∣−2∣E′∣∣E′∣∣V∣−∣E′∣得证。 G G G 的最大独立集加上最小点覆盖大小刚好为 ∣ V ∣ |V| ∣V∣。 证明对于 G G G 的最大独立集 V ′ V V′显然每条边最多只有一个端点属于 V ′ V V′。令 V ′ ′ V − V ′ VV-V V′′V−V′则每条边至少一个端点属于 V ′ ′ V V′′这刚好与点覆盖的定义相同即 V ′ ′ V V′′ 就是这张图的最小点覆盖。
二分图最大匹配模板。
建立超级源点 S S S 以及超级汇点 T T T将原图中的每个点 u u u 拆分为两个点 i n u , o u t u in_u,out_u inu,outu S S S 向每个 i n u in_u inu 连容量为 1 1 1 的边 u u u 最多匹配一个点每个 o u t u out_u outu 向 T T T 连容量为 1 1 1 的边 u u u 最多被一个点匹配。对于每个可能的匹配 ( u , v ) (u,v) (u,v)连 i n u → o u t v in_u\to out_v inu→outv 且容量为 1 1 1 的边。这样建出来的图跑最大流即为答案。
二分图有一个性质就是最大匹配等于最小点覆盖虽然笔者不会证明但是这意味着求出了二分图最大匹配就相当于求出了另外三个的值。
接下来就是例题。
例题一P4251。
这种每行选一个使得没有重复的列的题都有一个套路将行和列连边然后跑二分图最大匹配。
首先想到二分答案我们需要判断答案是否小于等于 x x x。将所有小于等于 x x x 的数置为可以选的容易用二分图最大匹配求出当前能最多选几个数最后判断是否大于等于 n − k 1 n-k1 n−k1 个数即可。
例题二P2764。
首先当每个点自成一条路径的时候当前的路径条数为 n n n可以考虑一条边 ( x , y ) ∈ E (x,y)\in E (x,y)∈E满足覆盖 x x x 的链没有后继覆盖 y y y 的链没有前驱。将这两条链合并起来自然会使路径数减一。
将每个点拆分为两个点 a x , b x a_x,b_x ax,bx a x a_x ax 被选相当于 x x x 有了后继 b x b_x bx 被选相当于 x x x 有了前驱发现每条边 ( x , y ) (x,y) (x,y) 相当于将 a x a_x ax 和 b y b_y by 匹配起来这就是典型的二分图最大匹配了。
现在的问题在于如何输出方案。不难发现在图中流往哪个边流相当于这条边两个端点在同一条链里面这样记录方案也非常简单了。
练习题CF1592F2。
Hall 定理
注此知识点几乎和网络流没有关系仅为对二分图的补充读者可以选择性阅读。
Hall 定理对于一张二分图 G ( V 1 , V 2 , E ) G(V_1,V_2,E) G(V1,V2,E)定义函数 f ( V ) ( V ∈ V 1 ) f(V)(V\in V_1) f(V)(V∈V1) 为与点集 V V V 中相邻点的并集那么二分图有完美匹配的充要条件为 ∀ V ⊆ V 1 , ∣ f ( V ) ∣ ≥ ∣ V ∣ \forall V\subseteq V_1,|f(V)|\ge |V| ∀V⊆V1,∣f(V)∣≥∣V∣。笔者暂时不会证明。
练习题CF338E。
