定义：

一组点集可以分为两部分，且每部分内各点互不相连，两部分的点之间可以有边。

判定：

所有回路的长度都是偶数，即不存在长度为奇数的环。

二分图最大匹配算法：匈牙利算法，时间复杂度，最坏 O（点数 × 边数）

//二分图匹配
//n为男生数目，m为女生数目
//line[i][j]第i个男生和第j个女生有关系
//g[i]第i个女生的对象
//注意used每次都要清零
int n,m,t;
int line[N][N],g[N],used[N];

bool findd(int x)
{
    for (int j=1;j<=m;j++)
    {
        if (line[x][j] && !used[j])
        {
            used[j]=1;
            if (g[j]==0 || findd(g[j]))
            {
                g[j]=x;
                return true;
            }
        }
    }
    return false;
}

int main()
{
    memset(g,0,sizeof g);
    memset(line,0,sizeof line);
    int u=0;
    for (int i=1;i<=n;i++)
    {
        memset(used,0,sizeof used);
        if  (findd(i)) u++;
    }
    cout<<u;
    return 0;
}

 

变种1： 最小点覆盖

定义：在二分图中求最少的点，让每条边都至少和其中的一个点关联，这就是二分图中的最小顶点覆盖。

结论：最小点覆盖 = 最大匹配

方案：

 

证明：

 

证明来自：http://www.matrix67.com/blog/archives/116

代码：

//a,b 为点覆盖的方案
int v[N]={0},q[N]={0},qq[N]={0};
void fang_an(int x)
{
    q[x]=1;
    for (int j=1;j<=m;j++)
    {
        if (line[x][j] && !qq[j] && g[j] && g[j]!=x)
        {
            qq[j]=1;
            fang_an(g[j]);
        }
    }
}
for (int i=1;i<=m;i++) if (g[i]) v[g[i]]=1;
for (int i=1;i<=n;i++) if (!v[i] && !q[i])fang_an(i);
for (int i=1;i<=n;i++) if (!q[i]) a.push_back(i);
for (int i=1;i<=m;i++) if(qq[i]) b.push_back(i);

 

变种2：DAG图的最小路径覆盖

 

定义：用尽量少的不相交简单路径覆盖有向无环图（DAG）G的所有顶点，这就是DAG图的最小路径覆盖问题。换句话说，就是选尽量少的边，报这些边都从起点走到终点，恰好能经过整个图的所有顶点，问你这些边的数量。

结论：DAG图的最小路径覆盖数=节点数（n）-最大匹配数（m）

 

 

变种3：二分图的最大点独立集

定义：实质是个点集，这个集合里的点无论怎样都两两相连不到一起，满足这个要求的点数最大的一个。

结论：最大独立集数=节点数（n）-最大匹配数（m）

 

 

二分图的最佳完美匹配

KM算法

最大顶标和等于最小权匹配

最小顶标和等于最大权匹配

// 要求最小权时取负
int numX, numY;	// 两侧结点数
int g[N+2][N+2], lx[N+2], ly[N+2], slack[N+2]; // 类型与权值保持一致
int my[N+2], visx[N+2], visy[N+2];
int Dfs(int x){
    visx[x]=1;
    for (int y=1; y<=numY; y++) if (!visy[y]){
        int temp=lx[x]+ly[y]-g[x][y];
        if (!temp){
            visy[y]=1;
            if (!my[y] || Dfs(my[y])){
                my[y]=x;
                return 1;
            }
        } else
            slack[y]=min(slack[y], temp);
    }
    return 0;
}
void KM(){
    memset(my, 0, sizeof(my));
    memset(lx, 0x80, sizeof(lx));
    memset(ly, 0, sizeof(ly));
    for (int i=1; i<=numX; i++)
        for (int j=0; j<=numY; j++)
            lx[i]=max(lx[i], g[i][j]);
    for (int x=1; x<=numX; x++){
        memset(slack, 0x7f, sizeof(slack));
        while (1){
            memset(visx, 0, sizeof(visx));
            memset(visy, 0, sizeof(visy));
            if (Dfs(x)) break;
            int Min=0x7fffffff;
            for (int i=1; i<=numY; i++) if (!visy[i])
                Min=min(Min, slack[i]);
            for (int i=1; i<=numX; i++) if (visx[i])
                lx[i]-=Min;
            for (int i=1; i<=numY; i++)
                if (visy[i]) ly[i]+=Min;
                else slack[i]-=Min;
        }
    }
    int ans=0;
    for (int i=1;i<=numY;i++) ans+=g[my[i]][i];
    //或者
    for (int i=1;i<=numX;i++) ans+=lx[i]+ly[i];
    return ans;
}