HDU2444 The Accomodation of Students(二分图最大匹配）

有n个关系，他们之间某些人相互认识。这样的人有m对。
你需要把人分成2组，使得每组人内部之间是相互不认识的。
如果可以，就可以安排他们住宿了。安排住宿时，住在一个房间的两个人应该相互认识。
最多的能有多少个房间住宿的两个相互认识。

先是要判断是否为二部图，然后求最大匹配。

学习一下模板~

#include<cstdio>

#include<cstring>

#include<vector>

#include<algorithm>

using namespace std;

const int maxn=;

vector<int> g[maxn];

int linker[maxn];

bool used[maxn];

int uN;

int matchs[maxn];

int cnt[maxn];

bool dfs (int u) {

    int i;

    for (i=;i<g[u].size();i++) {

        int v=g[u][i];

        if (!used[v]) {

            used[v]=true;

            if (linker[v]==-||dfs(linker[v])) {

                linker[v]=u;

                return true;

            }

        }

    }

    return false;

}

int hungary () {

    int res=;

    int u;

    memset(linker,-,sizeof(linker));

    for (u=;u<=uN;u++) {

        memset(used,false,sizeof(used));

        if (dfs(u)) res++;

    }

    return res;

}

bool judge (int x,int y) {

    int i;

    for (i=;i<g[x].size();i++) {

        if (cnt[g[x][i]]==) {

            cnt[g[x][i]]=-y;

            matchs[g[x][i]]=true;

            if (!judge(g[x][i],-y)) return false;

        }

        else if (cnt[g[x][i]]==y) return false;

    }

    return true;

}

bool matched () {

    int i;

    memset(matchs,false,sizeof(matchs));

    for (i=;i<=uN;i++) {

        if (g[i].size()&&!matchs[i]) {

            memset(cnt,,sizeof(cnt));

            cnt[i]=-;

            matchs[i]=true;

            if (!judge(i,-)) return false;

        }

    }

    return true;

}

int main () {

    int m;

    int i;

    int u,v;

    while (~scanf("%d %d",&uN,&m)) {

        for (i=;i<=uN;i++)

        if (g[i].size()) g[i].clear();

        while (m--) {

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

            g[u].push_back(v);

            g[v].push_back(u);

        }

        if (matched()) printf ("%d\n",hungary()/);

        else printf ("No\n");

    }

    return ;

}