当前位置: 首页 > news >正文

Hall定理学习笔记

内容

设二分图左部点点数为 \(x\),右部点点数为 \(y\),且满足 \(x<y\)。定义一张二分图的完备匹配为:对于任意一个左部点都有与之匹配的右部点。

\(\text{Hall}\) 定理的内容是:一张二分图有完备匹配,等价于对于任意左部点的集合 \(S\),满足 \(|\{y|\exists x\in S, 边 (x,y) 存在\}|\ge |S|\),即 \(S\) 的邻域大小(记为 \(N(S)\))不小于 \(S\) 本身。

证明

必要性显然。反证即可。

下面证明充分性。

用归纳法证明。当 \(n=1\)\(\text{Hall}\) 定理显然成立。
\(n>1\) 时,选取其中任意一对匹配的点删去,剩下的点仍然满足 \(\text{Hall}\) 定理。
于是由归纳法得证。

拓展

\(\text{Hall}\) 定理在带权情况下(一个点能和多个点匹配)仍然成立。将一个点拆成 \(a_i\) 个点即可。

二分图最大匹配等于 \(x+\min\{|S|-N(S)\}\)

应用

QOJ12015 撸猫

将源点向每只猫连边 \(p_i\),每只猫和每个集合连边 \(\infty\),再从每个集合向汇点连边 \(x_i\) 即可。然后发现这是一个二分图最大匹配的形式,于是用 \(\text{Hall}\) 定理求出每一个猫的集合对应的 \(c\),取最小值即可。用高维前缀和,时间复杂度 \(\mathcal{O}(n2^n)\)

要注意应当把 \(\sum\limits{x_i}\) 当做 \(1\)

#include <bits/stdc++.h>
using namespace std;
constexpr int N=1<<20;
constexpr double eps=1e-12;
int n;
double a[N],b[N];
signed main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cin>>n;cout<<fixed<<setprecision(8);for(int i=0;i<1<<n;i++){cin>>a[i];for(int j=0;j<n;j++)if((i>>j)&1)b[j]+=a[i];}for(int i=0;i<n;i++){for(int j=0;j<1<<n;j++){if((j>>i)&1)a[j]+=a[j^(1<<i)];}}double ans=1;for(int i=0;i<1<<n;i++){double s=0;for(int j=0;j<n;j++)if((i>>j)&1)s+=b[j];if(s<eps)continue;ans=min(ans,(1-a[((1<<n)-1)^i])/s);}cout<<ans<<'\n';return 0;
}

CF1519F Chests and Keys

题目的限制等价于花 \(c_{i,j}\) 的代价连一条 \(i\)\(j\) 的边,要求整张图满足对于任意的箱子集合 \(S\),有 \(\sum\limits_{i\in S}a_i\ge\sum\limits_{\exists i\in S,存在(i,j)}b_j\)

观察到这个限制与上面 \(\text{Hall}\) 定理的第一个扩展形式类似,于是可以转化为最大流问题。然后 \(a,b\) 的值域都很小直接 \(5\) 进制状压类似模拟最大流即可。时间复杂度 \(O(n5^{2m})\),跑不满。

#include <bits/stdc++.h>
using namespace std;
int n,m,a[6],b[6],c[6][6],p5[7],dp[7][15625];
bool check(int x,int y){for(int i=0;i<m;i++)if(y/p5[i]%5<x/p5[i]%5)return 1;for(int i=0;i<m;i++)if(y/p5[i]%5>b[i])return 1;return 0;
}
signed main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cin>>n>>m;for(int i=0;i<n;i++)cin>>a[i];for(int i=0;i<m;i++)cin>>b[i];for(int i=0;i<n;i++)for(int j=0;j<m;j++)cin>>c[i][j];p5[0]=1;for(int i=1;i<=m;i++)p5[i]=p5[i-1]*5;memset(dp,0x3f,sizeof(dp));int mask=0;for(int i=0;i<m;i++)mask+=b[i]*p5[i];dp[0][mask]=0;for(int i=1;i<=n;i++){for(int j=0;j<p5[m];j++){int s=0;for(int k=0;k<m;k++)s+=j/p5[k]%5;if(s!=a[i-1])continue;int sum=0;for(int k=0;k<m;k++)if(j/p5[k]%5)sum+=c[i-1][k];for(int k=0;k<p5[m];k++){if(check(j,k))continue;dp[i][k-j]=min(dp[i][k-j],dp[i-1][k]+sum);}}}int ans=0x3f3f3f3f;for(int i=0;i<p5[m];i++)ans=min(ans,dp[n][i]);cout<<ans<<'\n';return 0;
}

ARC076F Exhausted?

将每个人向每个在他范围内的坐标连边,则原问题相当于要加多少个点才能有完备匹配。完备匹配转化为最大匹配,然后就可以用第二个扩展形式,求的就是:

\[\max\{|S|-\max\limits_{i\in S}l_i+\min\limits_{i\in S}r_i-m-1\} \]

扫描线即可。

注意可能有区间不交的情况,所以至少加 \(n-m\) 个椅子。

#include <bits/stdc++.h>
using namespace std;
constexpr int N=2e5+5;
int n,m;
struct Node{int l,r;}a[N];
struct SegmentTree{int maxn[N<<2],tag[N<<2];#define ls(p) (p<<1)#define rs(p) (p<<1)|1void pushup(int p){maxn[p]=max(maxn[ls(p)],maxn[rs(p)]);}void pushdown(int p){maxn[ls(p)]+=tag[p];maxn[rs(p)]+=tag[p];tag[ls(p)]+=tag[p];tag[rs(p)]+=tag[p];tag[p]=0;}void update(int p,int l,int r,int val,int pl,int pr){if(l<=pl&&pr<=r){maxn[p]+=val;tag[p]+=val;return;}pushdown(p);const int mid=(pl+pr)>>1;if(mid>=l)update(ls(p),l,r,val,pl,mid);if(mid<r)update(rs(p),l,r,val,mid+1,pr);pushup(p);}int query(int p,int l,int r,int pl,int pr){if(l<=pl&&pr<=r)return maxn[p];pushdown(p);const int mid=(pl+pr)>>1;if(mid>=r)return query(ls(p),l,r,pl,mid);if(mid<l)return query(rs(p),l,r,mid+1,pr);return max(query(ls(p),l,r,pl,mid),query(rs(p),l,r,mid+1,pr));}
}tr;
signed main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cin>>n>>m;for(int i=1;i<=n;i++)cin>>a[i].l>>a[i].r;sort(a+1,a+n+1,[](Node x,Node y){return x.l<y.l||(x.l==y.l&&x.r>y.r);});for(int i=0;i<=m+1;i++)tr.update(1,i,i,i,0,m+1);int ans=max(0,n-m);for(int i=1;i<=n;i++){tr.update(1,0,a[i].r,1,0,m+1);ans=max(ans,tr.query(1,0,m+1,0,m+1)-a[i].l-m-1);}cout<<ans<<'\n';return 0;
}
http://www.hskmm.com/?act=detail&tid=28584

相关文章:

  • Vue3快速上手 - Ref
  • 象棋图片转FEN字符串详细教程
  • 面向对象抽象,接口多态综合-动物模拟系统
  • MinGW-即时入门-全-
  • 自然语言处理在风险识别中的应用
  • cat
  • qt everywhere souce code编译 - 实践
  • 2023 CCPC final G
  • 2025 年高可靠性测试设备/HALT/HASS/Halt/Hass/厂家制造商推荐榜:聚焦高效质量解决方案,助力企业产品升级
  • 八字手链人物传记计划——旭
  • 20232309 2025-2026-1 《网络与系统攻防技术》实验一实验报告
  • 亚马逊发布基于Linux的Vega OS电视系统,禁止侧载应用
  • .net9.0 JWT AUTH2.0 添加身份认证授权
  • 扣子系列教程
  • 解决vscode中用npm报错
  • MATLAB复杂曲线曲面造型及导函数实现
  • 2025 年最新月嫂培训机构推荐榜单:短期 / 精英 / 金牌 / 高端月嫂培训及就业推荐,精选优质机构
  • OOP-实验一
  • 达梦使用jemalloc内存分配器
  • 2025 年深圳/龙岗/龙华/罗湖/南山/旧房翻新/出租房/二手房/老房/装修公司推荐:聚焦品质与服务,助您轻松焕新家
  • 2025 年中频炉厂商最新推荐排行榜权威发布,深度剖析应达电气等优质企业核心优势及选购要点节能/智能/自动化成套/高效率/智能感应加热中频炉厂家推荐
  • 2025 年气体/实验室/调压/气路/减压阀厂家推荐榜:聚焦安全与专业,助力各行业精准选品
  • 摸鱼混子回归 - ZERO
  • vue3实现抓拍并上传
  • 2025 年国内润滑油厂商最新推荐榜:聚焦优质品牌实力,助力企业精准选品润滑油净化/过滤/回用/液压油润滑油过滤厂商推荐
  • 纯前端实现项目过期
  • 基于形态学的权重自适应图像去噪的MATLAB实现
  • 2025 年油水分离器 / 气液分离器 / 液固分离器 / 水分离器 / 油分离器厂家推荐:西安同大技术沉淀与流体净化解决方案解析
  • 2025 年过滤器厂家最新推荐排行榜:聚焦烛式 / 金属 / 非金属 / 化工 / 精密过滤器等多类型设备,精选优质品牌助企业高效选型液固/高效/气固/催化剂过滤器厂家推荐
  • OOP-实验1