hdu2444（判二分图+最大匹配）

传送门：The Accomodation of Students

题意：有n个学生，m对相互认识的，问能否分成两队，使得每对中没有相互认识的，如果可以求最大匹配，否则输出No。

分析：判断二分图用染色法，然后直接匈牙利算法求最大匹配。

#include <cstdio>

#include <cstring>

#include <string>

#include <cmath>

#include <iostream>

#include <algorithm>

#include <queue>

#include <cstdlib>

#include <stack>

#include <vector>

#include <set>

#include <map>

#define LL long long

#define mod 100000000

#define inf 0x3f3f3f3f

#define eps 1e-6

#define N 210

#define FILL(a,b) (memset(a,b,sizeof(a)))

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

#define PII pair<int,int>

using namespace std;

int vis[N],match[N],color[N];

vector<int>g[N];

int dfs(int u)

{

    for(int i=,sz=g[u].size(); i<sz; i++)

    {

        int v=g[u][i];

        if(!vis[v])

        {

            vis[v]=;

            if(match[v]==-||dfs(match[v]))

            {

                match[v]=u;

                return ;

            }

        }

    }

    return ;

}

int judge(int u,int fa,int state)

{

    color[u]=state;

    for(int i=,sz=g[u].size(); i<sz; i++)

    {

        int v=g[u][i];

        if(v==fa)continue;

        if(color[v]&&color[u]==color[v])return ;

        else if(!color[v]&&!judge(v,u,-state))return ;

    }

    return ;

}

int main()

{

    int n,m,u,v;

    while(scanf("%d%d",&n,&m)>)

    {

        FILL(g,);

        FILL(match,-);

        for(int i=;i<=n;i++)g[i].clear();

        for(int i=; i<=m; i++)

        {

            scanf("%d%d",&u,&v);

            g[u].push_back(v);

            g[v].push_back(u);

        }

        FILL(color,);

        bool flag=true;

        for(int i=; i<=n; i++)

            if(!color[i]&&g[i].size()>)

            {

                if(!judge(i,i,))

                {

                    flag=false;

                    break;

                }

            }

        if(!flag)

        {

            puts("No");

            continue;

        }

        int ans=;

        for(int i=; i<=n; i++)

        {

            FILL(vis,);

            if(dfs(i))ans++;

        }

        printf("%d\n",ans/);

    }

}