ZR 集训 Day27 - 匹配与网络流 · ooliver

一些笔记一些关系二分图匹配大小 = 最小点覆盖大小 = |V| - 二分图最大独立集。 DAG 最小路径覆盖 = |V| - 拆点图注最大匹配 = 偏序集最长反链（即在 DAG 上选出最大的两两不可到达的点集）。什么是拆点图？对于 DAG 中每一条边 u \rightarrow v，我们在新图中连无向边：(u_r,v_l)，则形成了一个二分图。这个二分图即原 DAG 的拆点图。 Hall 定理邻集定义： N(S) = { v \in Y \mid \exists u \in S,\ (u,v) \in E } N(S)：集合 S 的邻集，即 S 中所有顶点能一步到达的邻居的集合。 S：左侧顶点集合 X 的任意一个子集。 Y：二分图右侧的顶点集合。 E：二分图中所有边的集合。霍尔定理： \forall S \subseteq X,\quad |S| \le |N(S)| |S|：集合 S 中顶点的个数。 |N(S)|：集合 N(S) 中顶点的个数。 König-Hall 公式（最大匹配数）： \nu(G) = |X| - \max_{S \subseteq X} \big( |S| - |N(S)| \big) \nu(G)：最大匹配大小。 |X|：左侧顶点总数。 \max_{S \subseteq X}：在所有子集 S 中取最大值。缺陷形式： \delta = \max_{S \subseteq X} \big( |S| - |N(S)| \big) \nu(G) = |X| - \delta \delta：缺陷值，必须放弃的最少顶点数。网络流相关最大流 = 最小割平面图最小割 = 对偶图注最短路什么是对偶图？对偶图是与平面图相伴的一种图。在图论中，对偶图是通过将平面图的面转换为顶点，并将面之间的公共边转换为对偶图中的边来构造的。对偶图的构造方法选择顶点：在给定平面图的每个面中任选一个点作为对偶图的顶点。连接边：对于平面图中两个面共有的边，在对偶图中连接这两个面的顶点，并且连线穿过这条公共边。处理割边：如果平面图中的某条边是某个面的割边，则在对偶图中以该面的顶点作环，并让它与这条边相交。对偶图的性质顶点数：对偶图的顶点数等于原平面图的面数。边数：对偶图的边数等于原平面图的边数。面数：对偶图的面数等于原平面图的顶点数。度数关系：对偶图中顶点的度数等于原平面图中对应面的度数。 P6577 【模板】二分图最大权完美匹配模板题。代码： C++ #include using namespace std; typedef long long ll; const int N=505; const ll inf=2e18; int n,m; int match[N],pre[N]; bool vis[N]; ll la[N],lb[N],d[N],w[N][N]; void bfs(int u){ fill(d+1,d+1+n,inf); fill(vis+1,vis+1+n,0); int x,y=0,yy=0; match[y]=u; while(match[y]){ x=match[y]; ll delta=inf; vis[y]=1; for(int i=1;ila[x]+lb[i]-w[x][i]) d[i]=la[x]+lb[i]-w[x][i],pre[i]=y; if(d[i]>n>>m; fill(&w[1][1],&w[n+1][n+1],-inf); fill(la+1,la+1+n,-inf); for(int i=1,u,v,wis;i>u>>v>>wis; w[u][v]=max(w[u][v],ll(wis)); } cout `#include using namespace std; typedef long long ll; const int N=505; const ll inf=2e18; int n,m; int match[N],pre[N]; bool vis[N]; ll la[N],lb[N],d[N],w[N][N]; void bfs(int u){ fill(d+1,d+1+n,inf); fill(vis+1,vis+1+n,0); int x,y=0,yy=0; match[y]=u; while(match[y]){ x=match[y]; ll delta=inf; vis[y]=1; for(int i=1;in;i++){ if(vis[i]) continue; if(d[i]>la[x]+lb[i]-w[x][i]) d[i]=la[x]+lb[i]-w[x][i],pre[i]=y; if(d[i]delta) delta=d[i],yy=i; } for(int i=0;in;i++){ if(vis[i]) la[match[i]]-=delta,lb[i]+=delta; else d[i]-=delta; } y=yy; } while(y) match[y]=match[pre[y]],y=pre[y]; } ll km(){ for(int i=1;in;i++) for(int j=1;jn;j++) la[i]=max(la[i],ll(w[i][j])); for(int i=1;in;i++) bfs(i); ll res=0; for(int i=1;in;i++) res+=w[match[i]][i]; return res; } signed main(){ cin>>n>>m; fill(&w[1][1],&w[n+1][n+1],-inf); fill(la+1,la+1+n,-inf); for(int i=1,u,v,wis;im;i++){ cin>>u>>v>>wis; w[u][v]=max(w[u][v],ll(wis)); } coutkm()"\n"; for(int i=1;in;i++) coutmatch[i]" "; return 0; }` P14598 [COCI 2025/2026 #2] 搭塔 / Tornjevi 考虑对 i>j 且异色的两点连有向边，原题转换成求 DAG 最小路径覆盖问题。所以将原图进行拆点，变成一个二分图，左侧每个点都与右侧异色且长度大于自己的点连边。而我们需要对这个二分图求最大匹配，再套一个霍尔定理（上面有解释）可知： \begin{aligned} Ans&=n-\nu(G) \\ &=n- (n - \max_{S \subseteq X} \big( |S| - |N(S)| \big) ) \\ &=\max_{S \subseteq X} \big( |S| - |N(S)| \big) ) \end{aligned} 其中 X 就是左侧点集。不难发现对于这个 \max，两个颜色是独立的，所以可以看作是两个颜色的 \max 相加。因为 N(S) 一定是当前前缀异色积木的数量，否则枚举到当前前缀就没有意义了，那想要 S 最大，即把所有同色点都选上，这个可以前缀和一下。对于一个询问就相当于求区间 \max，可以用 ST 表解决。代码： C++ #include using namespace std; const int N=2e5+5; int n,q; int sum[N]; struct ST{ int st[N][20]; void init(){ for(int j=1;j>n>>q; for(int i=1;i>c; sum[i]=sum[i-1]+((c=='P')?1:-1); s1.st[i][0]=sum[i],s2.st[i][0]=-sum[i]; } s1.init(),s2.init(); while(q--){ int l,r; cin>>l>>r; cout `#include using namespace std; const int N=2e5+5; int n,q; int sum[N]; struct ST{ int st[N][20]; void init(){ for(int j=1;j19;j++) for(int i=0;in-(1j)+1;i++) st[i][j]=max(st[i][j-1],st[i+(1(j-1))][j-1]); } int get(int l,int r){ int k=log2(r-l+1); return max(st[l][k],st[r-(1k)+1][k]); } }s1,s2; signed main(){ cin>>n>>q; for(int i=1;in;i++){ char c; cin>>c; sum[i]=sum[i-1]+((c=='P')?1:-1); s1.st[i][0]=sum[i],s2.st[i][0]=-sum[i]; } s1.init(),s2.init(); while(q--){ int l,r; cin>>l>>r; couts1.get(l-1,r)+s2.get(l-1,r)"\n"; } return 0; }` P2764 最小路径覆盖问题上面有笔记，这里解释一下。每次合并两条路径，答案就会减 1，最开始的路径数量显然是 |V|，当我们建立拆点图，找到一个匹配 out_u,in_v，说明以 u 结尾的链与以 v 开头的链进行了合并操作，答案就减 1，所以我们对拆点图跑最大二分图匹配即可。代码： C++ #include using namespace std; const int N=305; int n,m,ans; int match[N],to[N],vis[N]; vector g[N]; bool dfs(int u){ for(int v:g[u]){ if(vis[v]) continue; vis[v]=1; if(!match[v]||dfs(match[v])){ match[v]=u,to[u]=v; return 1; } } return 0; } signed main(){ cin>>n>>m; for(int i=1,u,v;i>u>>v; g[u].push_back(v); } for(int i=1;i `#include using namespace std; const int N=305; int n,m,ans; int match[N],to[N],vis[N]; vectorint> g[N]; bool dfs(int u){ for(int v:g[u]){ if(vis[v]) continue; vis[v]=1; if(!match[v]||dfs(match[v])){ match[v]=u,to[u]=v; return 1; } } return 0; } signed main(){ cin>>n>>m; for(int i=1,u,v;im;i++){ cin>>u>>v; g[u].push_back(v); } for(int i=1;in;i++){ fill(vis+1,vis+1+n,0); vis[i]=1; if(dfs(i)) ans++; } for(int i=1;in;i++){ if(!match[i]){ int x=i; while(x!=0){ coutx" "; x=to[x]; } cout"\n"; } } coutn-ans; return 0; }` P3967 [TJOI2014] 匹配二分图最大权完美匹配。看到 n 的范围很小，想到第一问现跑一遍 KM，之后枚举一组解内的所有匹配边，如果删边之后答案变小了，说明这个边是必须要有的，就输出。代码： C++ #include using namespace std; const int N=85; const int inf=1e9; int n,m,ans; int match[N],pre[N]; bool vis[N]; int la[N],lb[N],d[N],w[N][N]; vector> pr; void bfs(int u){ fill(d+1,d+1+n,inf); fill(vis+1,vis+1+n,0); int x,y=0,yy=0; match[y]=u; while(match[y]){ x=match[y]; int delta=inf; vis[y]=1; for(int i=1;ila[x]+lb[i]-w[x][i]) d[i]=la[x]+lb[i]-w[x][i],pre[i]=y; if(d[i]>n; for(int i=1;i>w[i][j]; cout `#include using namespace std; const int N=85; const int inf=1e9; int n,m,ans; int match[N],pre[N]; bool vis[N]; int la[N],lb[N],d[N],w[N][N]; vectorpairint,int>> pr; void bfs(int u){ fill(d+1,d+1+n,inf); fill(vis+1,vis+1+n,0); int x,y=0,yy=0; match[y]=u; while(match[y]){ x=match[y]; int delta=inf; vis[y]=1; for(int i=1;in;i++){ if(vis[i]) continue; if(d[i]>la[x]+lb[i]-w[x][i]) d[i]=la[x]+lb[i]-w[x][i],pre[i]=y; if(d[i]delta) delta=d[i],yy=i; } for(int i=0;in;i++){ if(vis[i]) la[match[i]]-=delta,lb[i]+=delta; else d[i]-=delta; } y=yy; } while(y) match[y]=match[pre[y]],y=pre[y]; } int km(){ for(int i=1;in;i++) la[i]=-inf,match[i]=0; for(int i=1;in;i++) for(int j=1;jn;j++) la[i]=max(la[i],w[i][j]); for(int i=1;in;i++) bfs(i); int res=0; for(int i=1;in;i++) res+=w[match[i]][i]; return res; } signed main(){ cin>>n; for(int i=1;in;i++) for(int j=1;jn;j++) cin>>w[i][j]; cout(ans=km())"\n"; for(int i=1;in;i++) pr.push_back({match[i],i}); sort(pr.begin(),pr.end()); for(auto[u,v]:pr){ int wis=w[u][v]; w[u][v]=-inf; if(km()ans) coutu" "v"\n"; w[u][v]=wis; } return 0; }` P2053 [SCOI2007] 修车考虑把每个师傅修不同车的状态设置为左部点集，把所有车作为右部点集，跑二分图最大权匹配，但是因为修车可以同时进行，这个边权不好算。所以我们考虑设置状态时按照每个师傅修这辆车时是倒数第 k 个，这样对答案的贡献就是 k*t_{i,j}。代码： C++ #include using namespace std; const int N=550; const int inf=1e9; int n,m,ans; int match[N],pre[N]; bool vis[N]; int la[N],lb[N],d[N],w[N][N],t[N][N]; vector> pr; void bfs(int u){ fill(d+1,d+1+n,inf); fill(vis+1,vis+1+n,0); int x,y=0,yy=0; match[y]=u; while(match[y]){ x=match[y]; int delta=inf; vis[y]=1; for(int i=1;ila[x]+lb[i]-w[x][i]) d[i]=la[x]+lb[i]-w[x][i],pre[i]=y; if(d[i]>m>>n; for(int i=1;i>t[i][j]; for(int k=1;k `#include using namespace std; const int N=550; const int inf=1e9; int n,m,ans; int match[N],pre[N]; bool vis[N]; int la[N],lb[N],d[N],w[N][N],t[N][N]; vectorpairint,int>> pr; void bfs(int u){ fill(d+1,d+1+n,inf); fill(vis+1,vis+1+n,0); int x,y=0,yy=0; match[y]=u; while(match[y]){ x=match[y]; int delta=inf; vis[y]=1; for(int i=1;in;i++){ if(vis[i]) continue; if(d[i]>la[x]+lb[i]-w[x][i]) d[i]=la[x]+lb[i]-w[x][i],pre[i]=y; if(d[i]delta) delta=d[i],yy=i; } for(int i=0;in;i++){ if(vis[i]) la[match[i]]-=delta,lb[i]+=delta; else d[i]-=delta; } y=yy; } while(y) match[y]=match[pre[y]],y=pre[y]; } int km(){ for(int i=1;in;i++) la[i]=-inf,match[i]=0; for(int i=1;in;i++) for(int j=1;jn;j++) la[i]=max(la[i],w[i][j]); for(int i=1;in;i++) bfs(i); int res=0; for(int i=1;in;i++) res+=w[match[i]][i]; return res; } signed main(){ cin>>m>>n; for(int i=1;in;i++) for(int j=1;jm;j++){ cin>>t[i][j]; for(int k=1;kn;k++) w[i][(j-1)*n+k]=-k*t[i][j]; } n=m*n; coutfixedsetprecision(2)km()*(-1.0)/(n/m); retur…