企业 做网站,显示网站建设精美页面,wordpress 代码执行,长沙建设教育网官网二分图的基本概念#xff1a; 二分图又称作二部图#xff0c;是图论中的一种特殊模型。 设G(V,E)是一个无向图#xff0c;如果顶点V可分割为两个互不相交的子集(A,B)#xff0c;并且图中的每条边(i#xff0c;j)所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A,j …二分图的基本概念 二分图又称作二部图是图论中的一种特殊模型。 设G(V,E)是一个无向图如果顶点V可分割为两个互不相交的子集(A,B)并且图中的每条边(ij)所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A,j in B)则称图G为一个二分图。 比如 我们一般把图的两部分称为X部和Y部一个图的所有点如果能被两个独立的点集那就认为这个图是二分图 二分图的判断一般通过染色的方法来进行判段可以写成dfs或则bfs的写法 bool dfs(int v,int c)
{color[v]c;for(int i0;in;i){if(edge[v][i]1){if(color[i]c) return false;if(color[i]0!dfs(i,-c)) return false;}}return true;
}
void solve()
{int flag0;for(int i0;in;i){if(color[i]0){if(!dfs(i,1)){coutnoendl;flag1;break;}}} if(!flag) coutyesendl;
} bfs写法 bool bfs(int s)
{color[s] 1;queueint que;que.push(s);while(!que.empty()){int from que.front();que.pop();for(int i 1; i V; i){// 如果相邻的点没有上色就给这个点上色if(G[from][i] color[i] 0){que.push(i);color[i] -color[from];}// 如果相邻的颜色相同则返回falseif(G[from][i] color[i] color[from])return false;}}// 如果所有的点都被染过色且相邻的点颜色都不一样返回truereturn true;
} 接下来就是介绍匹配 一个匹配是一个边的集合任何匹配的边之间没有公共顶点。 最大匹配一个图的所有匹配中边数最多的匹配称为最大匹配。如果所有定点都是匹配顶点,则称这个匹配为完美匹配。 我们一般通过匈牙利算法来求一个二分图的最大匹配其算法的核心是求增广路径。 交替路从一个未匹配点出发依次经过非匹配边、匹配边、非匹配边...形成的路径叫交替路。* 增广路从一个未匹配点出发走交替路如果途径另一个未匹配点出发的点不算则这条交替路称为增广路agumenting path。 我们每次找到一个增广路所得到的匹配的边数都会增加一条因此我们可以通过求所有点的增广路径来求最大匹配的边数 匈牙利算法的模板如下 bool dfs(int x)
{for(int i1;ip;i){if(!used[i]map[x][i]1){used[i]1;if(!link[i]||dfs(link[i])){link[i]x;return true;}}}return false;
}
void xyl()
{for(int i1;in;i){memset(used,0,sizeof(used));if(dfs(i)) counts;}
} PS.练习题hdu 1045,hdu 2444,hdu 1083 此外还有二分图的最小顶点覆盖最大独立集最大团等知识求的方法和匈牙利算法的差不多可以参考如下博客 https://www.cnblogs.com/jianglangcaijin/p/6035945.html 剩下的带权二分图过几天在补充 转载于:https://www.cnblogs.com/tombraider-shadow/p/10945775.html
