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

二分图

顾名思义,二分图就是能将图分为两部分的图。这两部分满足只有不同部分间有边,同一部分内没边。这样的图存在许多优美的性质。然后大概就是下一次模拟赛再遇到二分图就不能拿没学过背锅了。

判定

直接定义法,DFS/BFS尝试给图染色。要求相邻点色不同。如果无法达到这种状态说明该图不是二分图。

模型

这里只着重讲讲匹配。匹配是很重要的算法。然后大概就是十分重要了。

匹配问题的根本是最大匹配。定义大概就是每个点只能连一条边,求最多能连多少条边。方法是匈牙利算法。思想就是钦定从一边开始匹配,每次寻找增广路,如果遇到一个另一边的点没有被匹配过或者当前另一边点的匹配点还能找到匹配点,就用该点与另一边点匹配。然后就能保证能匹配的都匹配了。时间复杂度是\(O(n^2)\) 的。

模板代码
#include<bits/stdc++.h>
using namespace std;
const int maxn=510,maxm=5e4+10;
int n,m,e;
int tot,to[maxm],nxt[maxm],h[maxn];
inline void adde(int x,int y){to[++tot]=y;nxt[tot]=h[x];h[x]=tot;
}
bool vis[maxn];
int match[maxn];
inline bool Find(int x){for(int i=h[x];i;i=nxt[i]){int y=to[i];if(!vis[y]){vis[y]=1;if(!match[y]||Find(match[y])){match[y]=x;return 1;}}}return 0;
}
int ans;
inline void hungary(){for(int i=1;i<=n;i++){memset(vis,0,sizeof(vis));if(Find(i)) ++ans;}
}
int main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cin>>n>>m>>e;for(int i=1,u,v;i<=e;i++){cin>>u>>v;adde(u,v);}hungary();cout<<ans;return 0;
}

然后有以下几点性质:
1.最小点覆盖集的大小等于最大匹配集的大小。说通俗点就是选择最少数量的点,使得每条边都有某个端点被选。
2.最大独立集=图的点数-最大匹配。说通俗点就是找出最大的集合内任意两点都没有边相连的集合。
3.最小路径覆盖数=原点数-拆点后的最大匹配。说通俗点就是求最少的路径,使所有的点都在路径上。拆点就是将每个节点拆成入点和出点。

然后二分图跟网络流比较相似的一点就是需要巧妙地建出图,然后剩下的东西一般就比较板了。然后确实一定数量的二分图的题可以用网络流做。但大部分情况下二分图时间复杂度更优。

(最大权匹配先鸽了)

http://www.hskmm.com/?act=detail&tid=37526

相关文章:

  • 2025不锈钢方形/消防/生活/保温水箱厂家推荐莞南节能,专业耐用品质保障
  • 2025-10-23 DeepSeek R1本地部署(ollama)
  • python 异步调用语法
  • KAPE 0.8.3.0发布:数字取证工具新版本详解
  • 第一!天翼云引领中国教育公有云市场
  • 哇哦杯题解民间版
  • 海上60公里,5G信号满格?这款神器让远航不再“失联”
  • 2025除尘设备/脉冲除尘器厂家推荐东莞市百谊环保科技,专业高效净化解决方案
  • 2025 年压滤机厂家最新推荐排行榜:隔膜 / 污泥 / 真空 / 板框 / 带式压滤机优质品牌权威指南
  • 2025发电机/发电机组/柴油发电机/甲醇发电机组租赁厂家推荐新疆泓浩机电,专业维修保养服务保障
  • 2025 年氮化硅陶瓷球生产厂家最新推荐榜:高精度高耐磨产品优选,国内优质企业全面剖析
  • 阿里云加持,《泡姆泡姆》让全球玩家畅享零延迟冒险
  • 基于粒子群优化(PSO)算法的PID控制器参数整定
  • VScodeC语言结构体成员提示不全
  • 2025滑石粉厂家推荐辽宁精华新材料,纳米级/工业级/化妆品级多品类覆盖
  • 上海结申管件制造有限公司:承插焊异径三通、承插焊Y型三通、高压承插管件、锻造承插三通源头厂家
  • 承插焊异径三通源头厂家推荐上海结申,专业制造高压承插管件
  • 【10.29 直播】IoTDB 图形化工具与编程框架集成实操
  • 锻造承插三通厂家专业技术对比,上海结申管件承压性能提升28%使用寿命延长35%
  • 2025棒球帽/卫衣/羽绒服品牌推荐,COVERNAT潮流服饰厂家精选
  • Windows 命令行查看COM口
  • harbor基于自建证书部署HTTPS及k8s集群
  • python练习 石头剪刀布
  • 基于 Spring AI Alibaba + Nacos 的分布式 Multi-Agent 构建指南
  • 【IEEE出版】第六届计算机通信与网络安全国际学术会议(CCNS 2025)
  • 2025 年最新推荐编织袋源头厂家排行榜:聚焦全自动智能节能设备,助力企业选对优质厂商工业 / 数控 / 重型 / 多功能 / 自动编织袋设备推荐
  • 2025年专业的上海Micro-LED显示屏推荐TOP生产厂家
  • 2025年质量好的工业不锈钢链轮最新TOP厂家推荐
  • 2025年正规的广州智能洗碗机,广州洗碗机设备厂家最新推荐榜
  • 改进的(μ+λ)约束差分进化算法设计与实现