hdu_2444The Accomodation of Students(二分图的判定和计算)

标签：二分图匹配

题目链接

题意：

问学生是否能分成两部分，每一部分的人都不相认识，如果能分成的话，两两认识的人可以去开房哈。求最大的开房数。

题解：

二分染色，黑白染色来看这个图可以被染成一个二分图，如果可以的话求出二分图匹配的个数即可

注意事项：

dfs来染色，在求解的时候注意点的编号是从0还是从1开始的

代码：

//二分图最好用链表存图
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 1010;
int vis[N];
int v[N];
int head[N];
struct Edge{
    int to;
    int next;
}edge[N*N];
int Ecnt;
int rm[N];
int id[N];
void init()
{
    Ecnt = 0;
    memset(vis,0,sizeof(vis));
    memset(id,-1,sizeof(id));
    memset(rm,-1,sizeof(rm));
    memset(v,0,sizeof(v));
    memset(head,-1,sizeof(head));
}
void add(int from, int to){
    edge[Ecnt].to = to;
    edge[Ecnt].next = head[from];
    head[from] = Ecnt++;
    edge[Ecnt].to = from;
    edge[Ecnt].next = head[to];
    head[to] = Ecnt++;
}
bool dfs(int s,int type){
    id[s] = type;
    for(int i = head[s]; i != -1; i = edge[i].next)
    {
        int t = edge[i].to;
        if(id[t]!=-1&&id[t]!=!type) return 0;
        if(v[t]==0){
            v[t] = 1;
           if( dfs(t,!type)==0) return 0;
        }
    }
    return 1;
}
int list(int s){
    for(int i = head[s]; i!= -1; i= edge[i].next){
        int t = edge[i].to;
        if(vis[t]) continue;
        vis[t] = 1;
        if(rm[t]==-1||list(rm[t])){
            rm[t] = s;
            return 1;
        }
    }
    return 0;
}
int Max_match(int n)
{
    int ans = 0;
    for(int i = 0; i < n; i++){
        memset(vis,0,sizeof(vis));
        vis[i] = 1;
        if(list(i)) ans++;
    }
    return ans;
}
int main()
{
    int n,m;
    int x, y;
    while(~scanf("%d%d",&n,&m))
    {
        init();
        for(int i = 0; i < m; i++){
            scanf("%d%d",&x,&y);
            x--;y--;//加边的时候要注意点的编号是从什么开始的
            add(x,y);
        }
        bool fl = 1;
        for(int i = 0; i < n; i++){
            if(v[i])continue;
            if(dfs(i,0)==0){fl = 0;continue;}
        }
        if(fl == 0) puts("No");
        else {
               // puts("haha");
            int ans = Max_match(n);
            printf("%d\n",ans/2);
        }
    }
    return 0;
}