首页 > 代码库 > 二分图搞法
二分图搞法
匈牙利算法
int dfs(int x){ for(int i=1;i<=m;i++){ if(!used[i]&&g[x][i]){ used[i]=1; if(link[i]==-1||dfs(link[i])){ link[i]=x; return 1; } } } return 0;}//用roll的话说就是,找女朋友,如果当前女生已经有男朋友了,就让这个男生去找另外一个女朋友,直到大家都找到为止。若找不到 这个点就没法匹配了。void solve(){ int ans=0; memset(link,-1,sizeof(link)); for(int i=1;i<=n;i++){ memset(used,0,sizeof(used)); if(dfs(i)) ans++; } printf("%d\n",ans);}
二分图的最小顶点覆盖数 = 二分图的最大匹配数
DAG(无回路有向图) 中
DAG图的最小路径覆盖数 = 节点数- 最大匹配数
二分图的最大独立集数 = 节点数 — 最大匹配数
最小点权覆盖: 拆点变成最小割,然后用最大流求解。
最大点权独立集:总权值-最小点权独立集
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。