HDOJ 2444 The Accomodation of Students

时间:2022-12-16 09:49:05

染色判读二分图+Hungary匹配

The Accomodation of Students

Time Limit: 5000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1705    Accepted Submission(s): 821

Problem Description
There are a group of students. Some of them may know each other, while others don't. For example, A and B know each other, B and C know each other. But this may not imply that A and C know each other.

Now you are given all pairs of students who know each other. Your task is to divide the students into two groups so that any two students in the same group don't know each other.If this goal can be achieved, then arrange them into double rooms. Remember, only paris appearing in the previous given set can live in the same room, which means only known students can live in the same room.

Calculate the maximum number of pairs that can be arranged into these double rooms.

 

Input
For each data set:
The first line gives two integers, n and m(1<n<=200), indicating there are n students and m pairs of students who know each other. The next m lines give such pairs.

Proceed to the end of file.

 

Output
If these students cannot be divided into two groups, print "No". Otherwise, print the maximum number of pairs that can be arranged in those rooms.
 

Sample Input
4 4
1 2
1 3
1 4
2 3
6 5
1 2
1 3
1 4
2 5
3 6
 

Sample Output
No
3
 

Source
 

Recommend
gaojie
 
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>

using namespace std;

typedef struct
{
    int to,next;
}Edge;

Edge E[50000];
int Adj[50000],Size=0,color[500],n,m,from[500];
bool use[500];

void Init()
{
    Size=0;
    memset(Adj,-1,sizeof(Adj));
}

void Add_Edge(int u,int v)
{
    E[Size].to=v;
    E[Size].next=Adj;
    Adj=Size++;
}

bool match(int x)
{
    for(int i=Adj[x];~i;i=E.next)
    {
        int v=E.to;
        if(!use[v])
        {
            use[v]=true;
            if(from[v]==-1||match(from[v]))
            {
                from[v]=x;
                return true;
            }
        }
    }
    return false;
}

int hungary()
{
    int sum=0;
    memset(from,-1,sizeof(from));
    for(int i=1;i<=n;i++)
    {
        if(color==1)
        {
            memset(use,false,sizeof(use));
            sum+=match(i);
        }
    }
    return sum;
}

int main()
{
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        int u,v;
        Init();
        while(m--)
        {
            scanf("%d%d",&u,&v);
            Add_Edge(u,v);
            Add_Edge(v,u);
        }
        memset(color,0,sizeof(color));
        bool flag=true;
while(true)
{
        int pos=-1;
        if(flag==false) break;
        for(int i=1;i<=n;i++)
        {
            if(Adj==-1) continue;
            else if(color!=0) continue;
            else
            {
                pos=i; break;
            }
        }
        if(pos==-1) break;
        queue<int> q;
        q.push(pos); color[pos]=1;
        //printf("%d: \n",pos);
        while(!q.empty())
        {
            if(flag==false) break;
            int u=q.front(); q.pop();
            for(int i=Adj;~i;i=E.next)
            {
                int v=E.to;
                //printf("%d--->%d\n",u,v);
                if(color[v]==0)
                {
                    color[v]=-color;
                    q.push(v);
                }
                else if(color[v]==color)
                {
                    flag=false; break;
                }
            }
        }
}
        if(flag==false)
        {
            puts("No");
        }
        else
        {
            printf("%d\n",hungary());
        }
    }
    return 0;
}

* This source code was highlighted by YcdoiT. ( style: Codeblocks )

HDOJ 2444 The Accomodation of Students的更多相关文章

  1. hdu 2444 The Accomodation of Students&lpar;最大匹配 &plus; 二分图判断)

    http://acm.hdu.edu.cn/showproblem.php?pid=2444 The Accomodation of Students Time Limit:1000MS     Me ...

  2. HDU 2444 The Accomodation of Students 二分图判定&plus;最大匹配

    题目来源:HDU 2444 The Accomodation of Students 题意:n个人能否够分成2组 每组的人不能相互认识 就是二分图判定 能够分成2组 每组选一个2个人认识能够去一个双人 ...

  3. hdu 2444 The Accomodation of Students 判断二分图&plus;二分匹配

    The Accomodation of Students Time Limit: 5000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K ( ...

  4. HDU 2444 The Accomodation of Students&lpar;判断二分图&plus;最大匹配&rpar;

    The Accomodation of Students Time Limit: 5000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K ( ...

  5. HDU——2444 The Accomodation of Students

    The Accomodation of Students Time Limit: 5000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K ( ...

  6. hdu 2444 The Accomodation of Students &lpar;判断二分图,最大匹配&rpar;

    The Accomodation of StudentsTime Limit: 5000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (J ...

  7. hdu 2444 The Accomodation of Students&lpar;二分匹配 匈牙利算法 邻接表实现&rpar;

    The Accomodation of Students Time Limit: 5000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K ( ...

  8. 【HDOJ】2444 The Accomodation of Students

    图论的题目.着色原理+二分图匹配. #include <cstdio> #include <cstring> #define MAXN 205 char map[MAXN][M ...

  9. (hdu)2444 The Accomodation of Students 判断二分图&plus;最大匹配数

    题目链接:http://acm.split.hdu.edu.cn/showproblem.php?pid=2444 Problem Description There are a group of s ...

随机推荐

  1. ActiveMQ学习(四)——应用程序接口

    在 Java 里有 JMS的多个实现.其中 apache 下的 ActiveMQ就是不错的选择. 用 ActiveMQ最好还是了解下 JMS JMS 公共 点对点域 发布/订阅域 Connection ...

  2. 在myeclipse10&period;7&period;1中写代码有很多红x

    代码没问题,但是很多代码前都有红x.在doc中执行都没有问题 jdk版本不对应    //第一步:菜单栏Window--Preferences--Java--Installed JREs--右边Add ...

  3. Android由一个activity 间隔5秒自动跳转到另外一个activity

    Android由一个activity 间隔5秒自动跳转到另外一个activity 2013年10月10日18:03:42 //一.写一个定时器 5秒后开启        final Intent lo ...

  4. &period;Net操作&period;exe文件

    Process proc = new Process(); proc.StartInfo.FileName = @"D:\Program Files\Foxmail\Foxmail.exe& ...

  5. latch介绍

    latch是一种锁,用来实现对Oracle所有共享数据结构的串行化访问.共享池就是这样一个例子, 这是系统全局区中一个庞大的共享数据结构,Oracle正是在这里存储已解析,已编译的SQL. 修改这个共 ...

  6. 理解 Javascript 的闭包

    什么是闭包 闭包是什么?闭包是Closure,这是静态语言所不具有的一个新特性.但是闭包也不是什么复杂到不可理解的东西,简而言之,闭包就是: 闭包就是函数的局部变量集合,只是这些局部变量在函数返回后会 ...

  7. CI的扩展机制

    CI的扩展机制 在熟悉了CI的源码之后,它的简单明了的代码风格很有趣,这篇文章看看在CI是如何实现扩展的. 扩展包 扩展是为了完成特定的功能,在CI中,扩展包的开发只能在application/lib ...

  8. swift3 控件创建

    //MARK:- UIScrollView let scrollView = UIScrollView() scrollView.delegate = target scrollView.backgr ...

  9. 刚入大学B&period; http&colon;&sol;&sol;mp&period;weixin&period;qq&period;com&sol;s&sol;ORpKfX8HOQEJOYfwvIhRew

    自己对计算机还是比较感兴趣的,经过不断的努力,我相信我可以在这一专业中显露头角,我会努力向博主学习.理想的大学是*,快乐,可以学到很多知识的地方,未来我想在lt行业进行软件开发等项目,为了梦想我会不 ...

  10. JS 多选文件或者选择文件夹

    <%--文件多选--%> <input type="file" name="file" id="file" multipl ...