HDU 2444 The Accomodation of Students (二分图匹配+匈牙利算法+bfs判断是否为二分图)

比眉伴天荒 2022-06-10 01:46 113阅读 0赞

There are a group of students. Some of them may know each other, while others don't. For example, A and B know each other, B and C know each other. But this may not imply that A and C know each other.  
  
Now you are given all pairs of students who know each other. Your task is to divide the students into two groups so that any two students in the same group don't know each other.If this goal can be achieved, then arrange them into double rooms. Remember, only paris appearing in the previous given set can live in the same room, which means only known students can live in the same room.  
  
Calculate the maximum number of pairs that can be arranged into these double rooms.

Input

For each data set:  
The first line gives two integers, n and m(1<n<=200), indicating there are n students and m pairs of students who know each other. The next m lines give such pairs.  
  
Proceed to the end of file.

Output

If these students cannot be divided into two groups, print "No". Otherwise, print the maximum number of pairs that can be arranged in those rooms.

Sample Input

4 4
    1 2
    1 3
    1 4
    2 3
    6 5
    1 2
    1 3
    1 4
    2 5
    3 6

Sample Output

No
    3

题解：

最近练二分图匹配，匈牙利算法，这题算是比较基础的，先用bfs找是否能分成两组，再用dfs版匈牙利算法求最大匹配数

代码：

#include<algorithm>
    #include<iostream>
    #include<cstring>
    #include<stdio.h>
    #include<math.h>
    #include<string>
    #include<stdio.h>
    #include<queue>
    #include<stack>
    #include<map>
    #include<deque>
    #define M (t[k].l+t[k].r)/2
    #define lson k*2
    #define rson k*2+1
    #define ll long long
    using namespace std;
    int col[205];//存每个人的组，本人为1，朋友为-1
    int vis[205];//遍历数组
    int p[205][205];//存朋友情况
    int used[205];//存和谁匹配
    int n;
    int judge()//判断是否为二分图
    {
        queue<int>q;
        int now,i;
        col[1]=1;//从1开始
        q.push(1);
        while(!q.empty())
        {
            now=q.front();
            q.pop();
            for(i=1;i<=n;i++)
            {
                if(now==i)
                    continue;
                if(!col[i]&&p[now][i])//如果是朋友并且没分组
                {
                    col[i]=-col[now];//和他分到不同的组
                    q.push(i);
                }
                else if(col[i]==col[now]&&p[now][i])//如果是朋友但是组的类别和他相同，返回0就是不能分组
                {
                    return 0;
                }
            }
        }
        return 1;
    }
    int find(int u)//dfs版匈牙利算法
    {
        int i,j;
        for(i=1;i<=n;i++)
        {
            if(!vis[i]&&p[u][i])//如果没被遍历并且是他的朋友
            {
                vis[i]=1;
                if(!used[i]||find(used[i]))//如果没分组或者是可以找到别人替代他并和该人匹配
                {
                    used[i]=u;
                    return 1;
                }
            }
        }
        return 0;//匹配失败
    }
    int main()
    {
        int m,i,j,x,y;
        while(scanf("%d%d",&n,&m)!=EOF)
        {
            memset(p,0,sizeof(p));
            memset(col,0,sizeof(col));//初始化
            memset(used,0,sizeof(used));
            for(i=0;i<m;i++)
            {
                scanf("%d%d",&x,&y);
                p[x][y]=1;//只一边赋值为1，因为反正是算对数，这里两边赋值和最后除2的结果是一样的
            }
            if(n==1||!judge())//不能分成两组的情况
            {
                printf("No\n");
                continue;
            }
            else
            {
                int ans=0;
                for(i=1;i<=n;i++)
                {
                    memset(vis,0,sizeof(vis));
                    if(find(i))
                        ans++;
                }
                printf("%d\n",ans);
            }
        }
        return 0;
    }