二分图总结

以下为我做题总结所得：

定义的作用是：判断某类问题能否用此类方法解决，所以定义的全面性，准确性非常重要！比如说定义手机，主要是用来远程通话的，如果我们需要

与别人联系就需要他了。而有手机做菜就不合适了！

二分图定义：边的两个端点分居两个集合中的图是二分图

二分图最大匹配的定义：①将所有边占有的最少端点数即最小覆盖②在无向图中图中无公共端点的最大边数③端点总数-最大无关系点数

以上是针对无向图来说的，而有向图则是一条最长且不相交的有向路径节数，图中所有这样路径的总条数是：顶点数-最大路径节数；

最大无关系点数定义：以最小覆盖为障碍，图中无关系的最大点数（关于点的）

算法我习惯于读代码，因为那样更透彻，然后思想自然明了了！

算法原理：

①定义点标记数组，定义边集；

②遍历判断定点说在边是否为交错路径（无公共端点的最大边集）的一部分，不是则递归dfs以改变原边集，以求符合

③是则记录入边集

其中的逆序边集用得最好

算法注意事项：二分图也可以有方向，方向不同的两条边，用全局变量时注意函数对它的影响；

算法代码示例：（以hdu1068为例http://acm.hdu.edu.cn/showproblem.php?pid=1068，红色部分为关键部分）

#include<stdio.h>//在二分图匹配中，edge【】存了匹配边，匹配边是无公共顶点的最大边数，即男女朋友的一对一特性且使，朋友的最少对数；

bool sign[1500];//标记顶点

int edge[1500];//edge[终边]=起始边

int map[1500][1500];//用的邻接表存储的图（但没用链表，没有发挥邻接表的优点——节省空间），其他方式也可以

int sum[1500];//与map[][]合为邻接表

bool isedge(int start)//判断是否能加入增广路径中

{

int i;

for(i=0;i<sum[start];i++){

//printf("/n%d,%d/n",start,map[start][i]);

if(sign[map[start][i]]==false){

sign[map[start][i]]=true;

if(edge[map[start][i]]==-1||isedge(edge[map[start][i]])){//以每个点为起点放最多的有向边（方向不能相抗）这是回路，方向边都遵循的

edge[map[start][i]]=start;

//printf("=%d,%d/n",start,map[start][i]);

return true;

}

}

}

return false;

}

main()

{

int n,i,j;

int start,num,end,answer;

while(scanf("%d",&n)!=-1){

for(i=0;i<n;i++)

sum[i]=0;

for(i=0;i<n;i++){

scanf("%d: (%d)",&start,&num);

for(j=0;j<num;j++){

scanf("%d",&end);

map[start][sum[start]++]=end;

}

}

answer=0;

for(i=0;i<n;i++)

edge[i]=-1;

for(i=0;i<n;i++){

for(j=0;j<n;j++)

sign[j]=false;

if(isedge(i))

answer++;

}

printf("%d/n",n-answer/2);

}

return 0;

}