寒假第六次训练-二分图

A - COURSES

题目大意：有n个学生和p门课，每门课程有0~n人参加，选定一人为课代表，课代表不能重复，问是否存在这样一群课代表使得每门课都有课代表

解题思路：匈牙利算法求二分图的最大匹配，若等于课程数则存在。

AC代码：

#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <map>
#include <vector>
#include <cstring>
#include <stack>
using namespace std;
#define MAXN 100005
bool G[110][310];
bool flag,visit[310];
int match[310];
int p,n;
bool dfs(int u)
{
    int v;
    for (v=1;v<=n;v++)
    {
        if (G[u][v] && !visit[v])
        {
            visit[v]=true;
            if (match[v]==-1 || dfs(match[v]))
            {
                match[v]=u;
                return true;
            }
        }
    }
    return false;
}
int main()
{
    int t,i,j,k,temp,ans;
    scanf("%d",&t);
    while (t--)
    {
        ans=0;
        flag=true;
        memset(G,false,sizeof(G));
        memset(match,-1,sizeof(match));
        scanf("%d%d",&p,&n);
        for (i=1; i<=p; i++)
        {
            scanf("%d",&j);
            if (j==0)
            {
                flag=false;
                break;
            }
            while (j--)
            {
                scanf("%d",&temp);
                G[i][temp]=true;
            }
        }
        if (flag)
        {
            for (i=1; i<=p; i++)
            {
                memset(visit,false,sizeof(visit));
                if (dfs(i)) ans++;
            }
            if (ans==p) printf("YES\n");
            else printf("NO\n");
        }
        else printf("NO\n");
    }
}

B - The Accomodation of Students

题目大意：有n个学生,m组学生相互认识，相互不认识的学生为一组，所有人分为两组，要求判断是否可以分为两组，若可以则把两组里互相认识的学生带入另一个房间，问最多可以带走多少组。

解题思路：先用染色法判断是否是二分图，然后用匈牙利算法求最大匹配

AC代码：

#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <map>
#include <vector>
#include <cstring>
#include <stack>
using namespace std;
#define MAXN 100005
bool G[210][210];
int color[210];
bool flag,visit[210];
int match[210];
int m,n;
bool paint(int i,int c)
{
    int v;
    color[i]=c+1;
    for (v=1; v<=n; v++)
    {
        if (G[i][v])
        {
            if (color[v])
            {
                if (color[v]==color[i])
                    return false;
                else continue;
            }
            else if (!paint(v,!(color[i]-1))) return false;
        }
    }
    return true;
}
bool dfs(int u)
{
    int v;
    for (v=1; v<=n; v++)
    {
        if (G[u][v] && !visit[v])
        {
            visit[v]=true;
            if (match[v]==-1 || dfs(match[v]))
            {
                match[v]=u;
                return true;
            }
        }
    }
    return false;
}
int main()
{
    int i,j,a,b,ans;
    while (scanf("%d%d",&n,&m)!=EOF)
    {
        ans=0;
        flag=true;
        memset(G,false,sizeof(G));
        memset(match,-1,sizeof(match));
        memset(color,0,sizeof(color));
        for (i=1; i<=m; i++)
        {
            scanf("%d%d",&a,&b);
            if (a!=b)
            {
                G[a][b]=true;
                G[b][a]=true;
            }
        }
        for (i=1;i<=n;i++)
        {
            if (!color[i]) flag=paint(i,0);
            if (!flag) break;
        }
        if (flag)
        {
            for (i=1; i<=n; i++)
            {
                if (color[i]==1)
                {
                    memset(visit,false,sizeof(visit));
                    if (dfs(i)) ans++;
                }
            }
            printf("%d\n",ans);
        }
        else printf("No\n");
    }
}