二分图 (匈牙利算法)
浏览数：25 /
时间：2015年06月08日
二分图的匈牙利算法
二分图的难点主要在建图；
关于二分图的几个重要公式：
最大匹配数=最小点覆盖
最小边覆盖=顶点总数-最大匹配数/2 （这个要拆点：uN=vN=cnt，ans=cnt-hungary/2)
最大团=补图最大独立集
最大独立集=顶点数-最大匹配
匈牙利算法：
int link[maxn]; vector<int>G [maxn]; int uN,vN; bool vis[maxn]; bool dfs(int u) { for(int i=0;i<G[u].size();i++){ //取出u的下一个未访问过的点v int v=G[u][i]; if(!vis[v]){ vis[v]=1; if(link[v]==-1||dfs(link[v])){ //如果link[v]==-1或dfs(link[v])，反转：link[v]=u; link[v]=u; return true; } } } return false; } int hungary() { int res=0; memset(link,-1,sizeof(link)); //初始化link数组 for(int u=1;u<=uN;u++){ memset(vis,0,sizeof(vis)); //注意每次需初始化vis数组 if(dfs(u)) res++; } return res; }
采用vector代替邻接矩阵模拟邻接表，提高效率又不增加代码量 (其实是我还没掌握好邻接表。。)
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
