hdoj 2444 The Accomodation of Students（裸的二分图判定+匈牙利）

题意：

一些学生之间是朋友关系（关系不能传递），现在要将一堆学生分成两堆,使得在同一堆的学生之间没有朋友关系。如果不可以输出“No”，可以的话输出最多可以分出几对小盆友（最大匹配）。

思路：

裸的二分图判定和匈牙利算法（匈牙利算法）

代码：

#include<bits/stdc++.h>using namespace std;const int maxn = 205;vector<int> e[maxn];int match[maxn], vis[maxn], n, m;bool judge(){    queue<int> q;    memset(vis, -1, sizeof(vis));    q.push(1);    vis[1] = 0;    while(q.size())    {        int u = q.front();        q.pop();        for(int i = 0; i < e[u].size(); i++)        {            int to = e[u][i];            if(vis[to] == -1)            {                vis[to] = !vis[u];                q.push(to);            }            else if(vis[to] == vis[u])                return false;        }    }    return true;}bool Find(int x){    for(int i = 0; i < e[x].size(); i++)    {        int to = e[x][i];        if(!vis[to])        {            vis[to] = 1;            if(match[to] == 0 || Find(match[to]))            {                match[to] = x;                return true;            }        }    }    return false;}int main(void){    while(cin >> n >> m)    {        for(int i = 0; i < maxn; i++)            e[i].clear();        memset(match, 0, sizeof(match));        for(int i = 1; i <= m; i++)        {            int x, y;            scanf("%d%d", &x, &y);            e[x].push_back(y);            e[y].push_back(x);        }        if(!judge()) puts("No");        else        {            int ans = 0;            for(int i = 1; i <= n; i++)            {                memset(vis, 0, sizeof(vis));                ans += Find(i);            }            PRintf("%d/n", ans/2);        }    }    return 0;}