二分图及最大匹配

860. 染色法判定二分图

•   题目 
•   提交记录 
•   讨论 
•   题解 
•   视频讲解 

给定一个 n

个点 m

条边的无向图，图中可能存在重边和自环。

请你判断这个图是否是二分图。

输入格式

第一行包含两个整数 n

和 m

。

接下来 m

行，每行包含两个整数 u 和 v，表示点 u 和点 v

之间存在一条边。

输出格式

如果给定图是二分图，则输出 Yes，否则输出 No。

数据范围

1≤n,m≤105

输入样例：

4 4
1 3
1 4
2 3
2 4

输出样例：

Yes

 * 先将任意一个顶点染成一种颜色，再将相邻顶点染成另一种颜色，重复每一个顶点（对于
 * 接下来还没有染色的点（此点一定和之前染过色的顶点不是连通的），任意染成一种颜色，
 * 将相邻的顶点染成另外一种颜色，）；如果对于每个顶点其相邻顶点的颜色都不相同，
 * 那么说明此图是二分图；

/**
 * 先将任意一个顶点染成一种颜色，再将相邻顶点染成另一种颜色，重复每一个顶点（对于
 * 接下来还没有染色的点（此点一定和之前染过色的顶点不是连通的），任意染成一种颜色，
 * 将相邻的顶点染成另外一种颜色，）；如果对于每个顶点其相邻顶点的颜色都不相同，
 * 那么说明此图是二分图；
*/
 
 
#include <iostream>
#include <algorithm>
#include <vector>
 
using namespace std;
 
const int maxn = 1e5+10;
vector<int> Adj[maxn];
int color[maxn];    //每个顶点是否着色
int Nv,Ne; //顶点数，边数
 
void Read() //读入数据
{
    cin >> Nv >> Ne;
    for(int i=0;i<Ne;++i)
    {
        int u,v;
        cin >> u >> v;
        Adj[u].push_back(v);
        Adj[v].push_back(u);
    }
}
 
int dfs(int u,int c) //对u这个顶点进行着色
{
    color[u]=c;
    for(int i=0;i<Adj[u].size();++i)    
    {
        int v=Adj[u][i];
        if(color[v]==0) //如果u的邻接点v还没有被着色
        {
            if(dfs(v,-c) == 0)      //如果对v着色冲突，即与u着了相同的颜色
                return 0;
        }
        else if(color[v]==color[u]) //如果v已经被着色，但是与u着了相同的颜色
            return 0;
    }
        
    return 1;   //没冲突
}
 
int is_bin_graph()
{
    for(int i=1;i<=Nv;++i)
    {
        if(color[i] == 0)
        {
            if(dfs(i,1) == 0)   //着色失败
                return 0;
        }
    }
    
    return 1; //着色成功，是二分图
}
 
int main()
{
    Read();
    
    if(is_bin_graph() == 1)
        puts("Yes");
    else    
        puts("No");
        
    return 0;
}

861. 二分图的最大匹配

•   题目 
•   提交记录 
•   讨论 
•   题解 
•   视频讲解 

给定一个二分图，其中左半部包含 n1

个点（编号 1∼n1），右半部包含 n2 个点（编号 1∼n2），二分图共包含 m

条边。

数据保证任意一条边的两个端点都不可能在同一部分中。

请你求出二分图的最大匹配数。

二分图的匹配：给定一个二分图 G

，在 G 的一个子图 M 中，M 的边集 {E} 中的任意两条边都不依附于同一个顶点，则称 M

是一个匹配。

二分图的最大匹配：所有匹配中包含边数最多的一组匹配被称为二分图的最大匹配，其边数即为最大匹配数。

输入格式

第一行包含三个整数 n1

、 n2 和 m

。

接下来 m

行，每行包含两个整数 u 和 v，表示左半部点集中的点 u 和右半部点集中的点 v

之间存在一条边。

输出格式

输出一个整数，表示二分图的最大匹配数。

数据范围

1≤n1,n2≤500

,
1≤u≤n1,
1≤v≤n2,
1≤m≤105

输入样例：

2 2 4
1 1
1 2
2 1
2 2

输出样例：

2

 
 * 虽然题目说每行包含两个整数 u 和 v，表示左半部点集中的点 u 和右半部点集中的点 v
 * 之间存在一条边。看着是无向边，但是处理起来，只能看作是单向边，因为是左部和右部
 * 相连，左部存在n1个顶点（ 1，2，……，n1），右部存在n2个顶点（1，2，……，n2）；
 * 处理成无向图，就不存在左部和右部之分，与题意不符合要求；

/**
 * 对于还没有匹配到“对象”的顶点v，这简单，直接让u和v匹配在一起就完事儿了；
 * 或者已经匹配到对象的顶点v，但是想给v换一个“对象”，这就有点麻烦了，得问问
 * v的对象match[v],看他是否有其他中意的人，让他去找其他人，如果能找到，那就让
 * match[v]和他中意的那个人，而v就从现任变为前任，转而让u和v在一起；
 * 如果一直搜索完所有人，都不能使v与match[v]分开，那么注定u与v是有缘无份，不能够
 * 在一起；
 * 以上就是dfs完成的操作：
*/

bool dfs(int u)
{
    for(int v=1;v<=n2;++v)  //遍历右半部分的顶点
    {
        if(hs[v]==0 && G[u][v]==1) //v还未被访问
        {
            hs[v]=1;    //记录v未被访问
            if(match[v]==0 || dfs(match[v])) //v还未被匹配或者给v换一个对象能够成功
            {
                match[v]=u; //因为是单向边，不是双向边，这一轮比较完以后，
                return 1;   //下一轮左边并不会用到u这个数；
            }
        }
    }
        
    return 0;
}

int max_bin_graph()
{
    int sum=0;
    for(int i=1;i<=n1;++i)
    {
        fill(hs,hs+maxn,0); //清除上一轮的标记
        if(dfs(i)==1)
            ++sum;
    }
    
    return sum;
            
}

/**
 * 虽然题目说每行包含两个整数 u 和 v，表示左半部点集中的点 u 和右半部点集中的点 v 
 * 之间存在一条边。看着是无向边，但是处理起来，只能看作是单向边，因为是左部和右部
 * 相连，左部存在n1个顶点（ 1，2，……，n1），右部存在n2个顶点（1，2，……，n2）；
 * 处理成无向图，就不存在左部和右部之分，与题意不符合要求；
*/
 
#include <iostream>
#include <cstring>
#include <algorithm>
 
using namespace std;
 
const int maxn = 510;
int G[maxn][maxn];  //邻接矩阵
int match[maxn];    //边匹配
int hs[maxn];   //顶点是否被访问
int n1,n2,m;
 
void Read()
{
    cin >> n1 >> n2 >> m;
    for(int i=0;i<m;++i)
    {
        int u,v;
        cin >> u >> v;
        G[u][v]=1;
    }
}
 
/**
 * 对于还没有匹配到“对象”的顶点v，这简单，直接让u和v匹配在一起就完事儿了；
 * 或者已经匹配到对象的顶点v，但是想给v换一个“对象”，这就有点麻烦了，得问问
 * v的对象match[v],看他是否有其他中意的人，让他去找其他人，如果能找到，那就让
 * match[v]和他中意的那个人，而v就从现任变为前任，转而让u和v在一起；
 * 如果一直搜索完所有人，都不能使v与match[v]分开，那么注定u与v是有缘无份，不能够
 * 在一起；
 * 以上就是dfs完成的操作：
*/
 
bool dfs(int u)
{
    for(int v=1;v<=n2;++v)  //遍历右半部分的顶点
    {
        if(hs[v]==0 && G[u][v]==1) //v还未被访问
        {
            hs[v]=1;    //记录v未被访问
            if(match[v]==0 || dfs(match[v])) //v还未被匹配或者给v换一个对象能够成功
            {
                match[v]=u; //因为是单向边，不是双向边，这一轮比较完以后，
                return 1;   //下一轮左边并不会用到u这个数；
            }
        }
    }
        
    return 0;
}
 
int max_bin_graph()
{
    int sum=0;
    for(int i=1;i<=n1;++i)
    {
        fill(hs,hs+maxn,0); //清除上一轮的标记
        if(dfs(i)==1) 
            ++sum;
    }
    
    return sum;
            
}
 
int main()
{
    Read();
    
    cout << max_bin_graph() << endl;
 
    return 0;
}

再增加一题：

12095. 4.2-2完美的牛栏

提高+/省选-

题目详情

题解

测评详情

农夫约翰上个星期刚刚建好了他的新牛棚，他使用了最新的挤奶技术。不幸的是，由于工程问题，每个牛栏都不一样。第一个星期，农夫约翰随便地让奶牛们进入牛栏，但是问题很快地显露出来：每头奶牛都只愿意在她们喜欢的那些牛栏中产奶。上个星期，农夫约翰刚刚收集到了奶牛们的爱好的信息（每头奶牛喜欢在哪些牛栏产奶）。一个牛栏只能容纳一头奶牛，当然，一头奶牛只能在一个牛栏中产奶。
给出奶牛们的爱好的信息，计算最大分配方案。

输入格式:

第一行 两个整数，N (0 <= N <= 200) 和 M (0 <= M <= 200) 。N 是农夫约翰的奶牛数量，M 是新牛棚的牛栏数量。



第二行到第N+1行 一共 N 行，每行对应一只奶牛。第一个数字 (Si) 是这头奶牛愿意在其中产奶的牛栏的数目 (0 <= Si <= M)。后面的 Si 个数表示这些牛栏的编号。牛栏的编号限定在区间 (1..M) 中，在同一行，一个牛栏不会被列出两次。

输出格式:

只有一行。输出一个整数，表示最多能分配到的牛栏的数量。

样例 1 :

输入:
5 5
2 2 5
3 2 3 4
2 1 5
3 1 2 5
1 2

输出:
4

照猫画虎：二分图的最大匹配

#include <iostream>
#include <algorithm>
 
using namespace std;
 
const int maxn = 210;
int G[maxn][maxn];
int match[maxn];
bool hs[maxn];
int n,m;
 
void Read()
{
    cin >> n >> m;
    for(int i=1;i<=n;++i)
    {
        int cnt;
        cin >> cnt;
        for(int j=0;j<cnt;++j)
        {
            int x;
            cin >>x;
            G[i][x]=1;
        }
    }
}
 
bool dfs(int u)
{
    for(int v=1;v<=m;++v)
        if(hs[v]==0 && G[u][v]==1)
        {
            hs[v]=1;
            if(match[v]==0 || dfs(match[v]))
            {
                match[v]=u;
                return 1;
            }
        }
    return 0;
}
 
int max_bin_graph()
{
    int sum=0;
    for(int i=1;i<=n;++i)
    {
        fill(hs,hs+maxn,0);
        if(dfs(i))
            ++sum;
    }
    return sum;
}
int main()
{
    Read();
 
    cout << max_bin_graph() << endl;
 
    return 0;
}