1 二分图的基本概念

二分图：整个图能被划分为两个点集（X,Y）且在同一点集内的所有点互不相交的图就是二分图。

匹配：在二分子图的边集M中如果M中的每条边的两个端点只有该条边与这两个端点相连，则M称为一个匹配。

匹配边：我们把两个相匹配的点之间的连线称为匹配边。

最大匹配：图中包含边数最多的匹配称为图的最大匹配。

完备匹配：如果有一边的点全都是匹配点，则称这个匹配为完备匹配。

完美匹配：如果所有点都在匹配边上，称这个最大匹配是完美匹配。

最小覆盖：用最少的点（Ｘ集合或Ｙ集合的都行）让每条边都至少和其中一个点关联。（也就是说每个边至少有一个端点是匹配点）

路径：就是连着的几条边（1—->2—->3就是一条路径）

最小路径覆盖问题：在有向无环图中，用最少的路径条数（不相交的路径，即不仅不能有重合的边，连重合的点都没有）覆盖掉所有顶点。

最大独立集问题：在Ｎ个点的图G中选出m个点，使这m个点两两之间没有边．求m最大值．（如果图Ｇ满足二分图条件）可以用二分图匹配来做．

关于二分图带权匹配&最大匹配&完备匹配&完美匹配的区分：

带权匹配：使得该二分图的权值和最大（或最小）的匹配。

最大匹配：使得该二分图边数最多的匹配。

完备匹配：使得点数较小的点集中每个点都被匹配的匹配。

完美匹配：所有点都被匹配的匹配。

可知：完美匹配一定是最大匹配和完备匹配。

二分图的判定：

1.如果一个图是有向无环图，则必定可以化成二分图，方法过后再讲。

2.无向图G为二分图的充要条件是，G至少有两个顶点,且其所有回路的长度均为偶数。

3.黑白染色：从一个没有染过色的点开始染色，把起始点染为黑色，与其连接的边的另一端点都染为白色，再从这些点开始继续染色，如果染色时发现该点已经被染色并且颜色和其相邻的点相同，则不是二分图。

思路：

最小路径覆盖问题解答便由此而来，路径数S=N-最大匹配。

最大独立集问题：m=N-最大匹配。

二分图(不带权)最大匹配：匈牙利算法。

二分图带权最优匹配：KM算法。

二、匈牙利算法

下面开始匈牙利算法的讲解：

如果当前存在未匹配点，那么则将该点（叫做点a好了）和其中一个与之相连的未匹配点进行匹配，如果与该点相连的都是匹配点，那么看在该点之前的点（点b）能不能(通过改变它的匹配边)把点a和点b的公共匹配点让给该点并将点b的仍有匹配边，如果能改变其匹配边，则进行改变，然后把点a与让出来的那个点进行匹配，若之前的都不能改变，则直接进行下一个点的选择，放弃点a。

进行第一步的操作后：

进行第二步的操作后：

结束算法。

总之，匈牙利算法是秉承着一种“能连就连，能不改就不改”的原则的。

算法模板：

dfs

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             using namespace std;const int maxn=1005;int n,m;bool used[maxn];int lt[maxn][maxn];int link[maxn];bool dfs(int u) { for(int i=1; i<=n; i++) { if(lt[u][i]&&!used[i]) { used[i]=1; if(link[i]==-1||dfs(link[i])) { link[i]=u; return 1; } } } return 0;}int main () { scanf("%d%d",&n,&m); for(int i=1; i<=m; i++) { int u,v,w; scanf("%d%d",&u,&v); lt[u][v]==1; //无论是有向图还是无向图我们都这样存，因为转换成二分图求最大匹配边数时其匹配边数都相等 而如果习惯无向图存两次的话，那么最大匹配数要>>1; } 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",ans); return 0;}

下面给出匈牙利算法的 DFS 和 BFS 版本的代码：// 顶点、边的编号均从 0 开始// 邻接表储存struct Edge{    int from;    int to;    int weight;    Edge(int f, int t, int w):from(f), to(t), weight(w) {}};vector
   
     G[__maxNodes]; /* G[i] 存储顶点 i 出发的边的编号 */vector
    
      edges;typedef vector
     
      ::iterator iterator_t;int num_nodes;int num_left;int num_right;int num_edges;int matching[__maxNodes]; /* 存储求解结果 */int check[__maxNodes];bool dfs(int u){    for (iterator_t i = G[u].begin(); i != G[u].end(); ++i) { // 对 u 的每个邻接点        int v = edges[*i].to;        if (!check[v]) {     // 要求不在交替路中            check[v] = true; // 放入交替路            if (matching[v] == -1 || dfs(matching[v])) {                // 如果是未盖点，说明交替路为增广路，则交换路径，并返回成功                matching[v] = u;                matching[u] = v;                return true;            }        }    }    return false; // 不存在增广路，返回失败}int hungarian(){    int ans = 0;    memset(matching, -1, sizeof(matching));    for (int u=0; u < num_left; ++u) {        if (matching[u] == -1) {            memset(check, 0, sizeof(check));            if (dfs(u))                ++ans;        }    }    return ans;}queue
      
        Q;int prev[__maxNodes];int Hungarian(){    int ans = 0;    memset(matching, -1, sizeof(matching));    memset(check, -1, sizeof(check));    for (int i=0; i
       
        = 0) { // 此点为匹配点                            prev[matching[v]] = u;                        } else { // 找到未匹配点，交替路变为增广路                            flag = true;                            int d=u, e=v;                            while (d != -1) {                                int t = matching[d];                                matching[d] = e;                                matching[e] = d;                                d = prev[d];                                e = t;                            }                        }                    }                }                Q.pop();            }            if (matching[i] != -1) ++ans;        }    }    return ans;}

KM算法：求在一个二分图的完备匹配中的最大权值匹配的算法。（下文简称为最佳完备匹配）

似乎跟匈牙利算法有点相似，

所以我们要引入一个基于匈牙利算法的一种算法，叫做KM算法。

步骤如下：

首先用邻接矩阵存储二分图，注意：如果只想求最大权值匹配而不要求是完备匹配的话，请把各个不相连的边的权值设置为0。

之后进行下述步骤：

1.运用贪心算法初始化标杆。

2.运用匈牙利算法找到完备匹配。

3.如果找不到，则通过修改标杆，增加一些边。

4.重复2，3的步骤，找到完备匹配时可结束。

#include
   
    #include
    
     #include
     
      using namespace std;const int qwq=0x7fffffff;int w[1000][1000];  //w数组记录边权值 int line[1000],usex[1000],usey[1000],cx[1000],cy[1000];  //line数组记录右边端点所连的左端点， usex，usey数组记录是否曾访问过，也是判断是否在增广路上，cx，cy数组就是记录点的顶标 int n,ans,m;  //n左m右 bool find(int x){    usex[x]=1;    for (int i=1;i<=m;i++){        if ((usey[i]==0)&&(cx[x]+cy[i]==w[x][i])){   //如果这个点未访问过并且它是子图里面的边             usey[i]=1;            if ((line[i]==0)||find(line[i])){   //如果这个点未匹配或者匹配点能更改                 line[i]=x;                return true;            }        }    }    return false;}int km(){    for (int i=1;i<=n;i++){  //分别对左边点依次匹配         while (true){        int d=qwq;        memset(usex,0,sizeof(usex));        memset(usey,0,sizeof(usey));        if (find(i)) break;  //直到成功匹配才换下一个点匹配         for (int j=1;j<=n;j++)            if (usex[j])             for (int k=1;k<=m;k++)             if (!usey[k]) d=min(d,cx[j]+cy[k]-w[j][k]);  //计算d值         if (d==qwq) return -1;          for (int j=1;j<=n;j++)         if (usex[j]) cx[j]-=d;           for (int j=1;j<=m;j++)         if (usey[j]) cy[j]+=d;     //添加新边        }    }    ans=0;    for (int i=1;i<=m;i++)     ans+=w[line[i]][i];    return ans;}int main(){    while (~scanf("%d%d",&n,&m)){    memset(cy,0,sizeof(cy));    memset(w,0,sizeof(w));    memset(cx,0,sizeof(cx));    for (int i=1;i<=n;i++){     int d=0;     for (int j=1;j<=n;j++){      scanf("%d",&w[i][j]);      d=max(d,w[i][j]);   //此处顺便初始化左边点的顶标        }    cx[i]=d;    }    memset(line,0,sizeof(line));    printf("%d\n",km());}    return 0;}

转载地址：http://uvki.baihongyu.com/

你可能感兴趣的文章

1 二分图的基本概念

二 、匈牙利算法

二、匈牙利算法