首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >I'm Telling the Truth(二分图)- HDU 3729

I'm Telling the Truth(二分图)- HDU 3729

作者头像
ACM算法日常
发布于 2018-08-07 10:15:22
发布于 2018-08-07 10:15:22
32600
代码可运行
举报
文章被收录于专栏:ACM算法日常ACM算法日常
运行总次数:0
代码可运行

二分图:设G=(V,E)是一个无向图,如果顶点V可分割为两个互不相交的子集(A,B),并且图中的每条边(i,j)所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A,j in B),则称图G为一个二分图

简单的说,一个图被分成了两部分,相同的部分没有边,那这个图就是二分图,二分图是特殊的图。

Problem Description

After this year’s college-entrance exam, the teacher did a survey in his class on students’ score. There are n students in the class. The students didn’t want to tell their teacher their exact score; they only told their teacher their rank in the province (in the form of intervals).

这学期的考试完了,老师在班上做了一个小调查:班上有n个学生,但是学生不想告诉老师自己考了多少分,他们只是告诉老师他们的成绩所在的区间。

After asking all the students, the teacher found that some students didn’t tell the truth. For example, Student1 said he was between 5004th and 5005th, Student2 said he was between 5005th and 5006th, Student3 said he was between 5004th and 5006th, Student4 said he was between 5004th and 5006th, too. This situation is obviously impossible. So at least one told a lie. Because the teacher thinks most of his students are honest, he wants to know how many students told the truth at most.

当问完所有的学生,老师发现有些学生撒谎了。比如,学生1号说他在5004到5005这两名中,学生2说他在5005到5006这两名中,学生3说他在5004到5006这3名中,学生4也说他在5004-5006。显然这种情况有问题,至少有一个学生撒谎了。老师认为大部分学生还是诚实的,所以他想知道有多少个学生说的是真话。

Input

There is an integer in the first line, represents the number of cases (at most 100 cases). In the first line of every case, an integer n (n <= 60) represents the number of students. In the next n lines of every case, there are 2 numbers in each line, Xi and Yi (1 <= Xi <= Yi <= 100000), means the i-th student’s rank is between Xi and Yi, inclusive.

第一行输入一个数,表示用例个数。

每个用例的第一行是学生n的个数,下面n行表示每个学生说的区间。

Output

Output 2 lines for every case. Output a single number in the first line, which means the number of students who told the truth at most. In the second line, output the students who tell the truth, separated by a space. Please note that there are no spaces at the head or tail of each line. If there are more than one way, output the list with maximum lexicographic. (In the example above, 1 2 3;1 2 4;1 3 4;2 3 4 are all OK, and 2 3 4 with maximum lexicographic)

每个用例输出2行,第一行输出最有有多少个学生说真话。

第二行输出说真话的学生,空格隔开。注意开头和结尾没有空格。如果有多个结果,输出词法上最大的那组。

Sample Input

2

4

5004 5005

5005 5006

5004 5006

5004 5006

7

4 5

2 3

1 2

2 2

4 4

2 3

3 4

Sample Output

3

2 3 4

5

1 3 5 6 7

解题思路:将每个学生报的名次区间作为二分图的左边,右边为所有名次,如果左边的区间顶点对应右边一个顶点,则表示该名次被占用。

解题虽然是二分图的思想,但是实现代码使用了数组链表,性能很好,能够做到0AC。具体参考源代码。

解题方法精要:从最后一个同学开始遍历,每次寻找空位,找到就返回。如果没有找到,A同学就mark标记一下表示这个位置X正在查找,然后深度搜索其他同学是否能够找到别的位置Y,如果同学B能找到,则B使用另外一个位置Y,那么A同学就使用这个位置X。

源码:G++ 0ms HDU排名19

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
#include<stdio.h>
#include<string.h>
#include<queue>
#include<iostream>

using namespace std;

typedef struct rank_s {
    int value;
    int prev;
} rank_t;

//数组-链表节点
rank_t ranks[100001];

int student_ids[100001], mark[100001], list_index[100], matches[100];

int find(int student_id, queue<int> & values)
{
    //遍历链表
    for (int i = list_index[student_id]; i != -1; i = ranks[i].prev)
    {
        //获得链表元素,value是排名
        int value = ranks[i].value;

        //排名是否被占用
        if (mark[value] == 0)
        {
            //标记占用
            mark[value] = 1;
            values.push(value);

            //排名指向的学生id
            if (student_ids[value] == 0)
            {
                student_ids[value] = student_id;
                return 1;
            }
            else {
                //深度搜索占用排名的学生是否能够找到别的排名
                if (find(student_ids[value], values) == 1)
                {
                    //如果能找到,则自己占用这个排名
                    student_ids[value] = student_id;
                    return 1;
                }
            }
        }
    }
    return 0;
}

int main()
{
    int test_count, student_count, sum;
    queue<int> values;

    //用例个数
    scanf("%d", &test_count);

    while (test_count--)
    {
        while (values.size()) {
            values.pop();
        }

        int current = 0;

        //输入学生数量
        scanf("%d", &student_count);

        memset(student_ids, 0, sizeof(student_ids));
        memset(list_index, -1, sizeof(list_index));
        memset(matches, -1, sizeof(matches));

        //输入学生说的区间
        for (int i = 1; i <= student_count; i++)
        {
            int a, b;
            scanf("%d%d", &a, &b);
            for (int j = a; j <= b; j++)
            {
                //数组链表
                ranks[current].value = j;
                ranks[current].prev = list_index[i];
                list_index[i] = current++;
            }
        }

        sum = 0;

        //从最后一个学生开始遍历
        for (int i = student_count; i >= 1; i--)
        {
            if (find(i, values) == 1) {
                //找到
                sum++;
                //记录匹配的学生id
                matches[i] = 1;
            }

            //清空标记
            while (values.size())
            {
                mark[values.front()] = 0;
                values.pop();
            }
        }

        printf("%d\n", sum);

        for (int i = 1; i <= student_count; i++)
        {
            if (matches[i] == 1)
            {
                printf("%d%s", i, sum == 1 ? "\n" : " ");
                sum--;
            }
        }
    }
}
本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2018-04-28,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 ACM算法日常 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
二分图详解
       本篇博客主要讲解什么是二分图,怎样判断二分图,匈牙利算法和HK(Hopcroft-Karp)算法,以及二分图多重匹配。
Ch_Zaqdt
2019/01/10
2.4K0
图论--二分图--二分图的定义及其判断定
如果一张无向图的N个节点(N>=2)可以分成A B两个非空子集,其中A∩B=Ø,并且在同一集合内的点之间没有相连的边,则称这张无向图为二分图。A,B分别成为这个图的左部和右部。
风骨散人Chiam
2020/10/28
1.2K0
图论--二分图--二分图的定义及其判断定
二分图匹配详解
二分图又称作二部图,是图论中的一种特殊模型。 设G=(V,E)G=(V,E)是一个无向图。如顶点集VV 可分割为两个互不相交的子集,并且图中每 条边依附的两个顶点都分属两个不同的子集。则称图GG 为二分图。我们将上边顶点集合称 为XX 集合,下边顶点结合称为YY 集合,如下图,就是一个二分图。
风骨散人Chiam
2020/10/28
1K0
二分图匹配详解
MySQL基础教程:全面理论与实践指南
MySQL是世界上最流行的开源关系型数据库管理系统之一,广泛应用于网站、应用程序和企业级系统。它采用客户端/服务器架构,支持多用户环境,并基于SQL(结构化查询语言)标准。
Lethehong
2025/04/28
1.2K0
MySQL基础教程:全面理论与实践指南
Leetcode|并查集|785. 判断二分图
1 并查集 遍历每个节点对应的邻接点,将每个邻接点通过并查集聚类 同时检查顶点是否与邻接点被聚到1类,若是则不满足二分图性质 注意孤立点判断 class UnionFind { public: int count; vector<int> parent, size; UnionFind(int n) { count = n; parent.resize(n); size.resize(n); for (int
SL_World
2021/09/22
4950
Leetcode|并查集|785. 判断二分图
C++ 图进阶系列之剖析二分图的染色算法和匈牙利算法
二分图的定义已经说明,图中存在二个独立的子集,为了区分这两个子集,可以给其中一个子集中的顶点染上红色,另一个子集中的顶点染上蓝色。具体是什么颜色并不重要,只要能区分就可以。
一枚大果壳
2023/08/18
5700
C++ 图进阶系列之剖析二分图的染色算法和匈牙利算法
二分图最大匹配
二分图也叫二部图,设G=(V,E)是一个无向图,如果顶点V可分割为两个互不相交的子集(A,B),并且图中的每条边(i,j)所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A,j in B),则称图G为一个二分图。如下图所有的顶点可以分成A,B两个集合,而A集合与B集合中的点与自己的阵营的点是没有连线的(A集合的点只与B集合的点有边相连),则称这个为一个二分图.(离散数学中的内容)
AngelNH
2020/04/16
1.3K0
二分图最大匹配问题
  二分图是这样的一个图:其顶点可以划分为两个集合 X 和 Y , 任何一条边所关联的两个顶点中,恰好有一个属于集合 X , 另一个属于 Y。同一个集合内的顶点必没有边相连。如果一个图是二分图,那么它一定没有 奇环 (边为奇数的环路),如果一个图没有 奇环 , 那么它就一定是 二分图。
yhlin
2023/02/27
6310
二分图最大匹配问题
HDU 2444 The Accomodation of Students(二分图判断+最大匹配数)
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2444        题意是有n个人,m个配对,问能不能根据m个将这些人分成两个集合,且集合中的任意两人
Ch_Zaqdt
2019/01/11
6030
从二进制枚举 follow up 到二分图判定,有点意思
不过我在评论区看到有人提到了 T4 对应的 follow-up 题,是 codeforces div2 的 D 题,涉及到了图论建模和二分图判定,一起来看一看吧
ACM算法日常
2022/02/10
4070
匈牙利算法(二分图最大匹配问题)
匈牙利算法用于求解无权二分图(unweighted bipartite graph)的最大匹配(maximum matching)问题
mathor
2019/12/30
1.5K0
匈牙利算法(二分图最大匹配问题)
最全二分图总结(最大匹配、最大权匹配、点覆盖、独立集、路径覆盖,带证明和例题)
二分图又称作二部图,是图论中的一种特殊模型。 设G=(V,E)是一个无向图,如果顶点V可分割为两个互不相交的子集(A,B),并且图中的每条边(i,j)所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A,j in B),则称图G为一个二分图。简而言之,就是顶点集V可分割为两个互不相交的子集,并且图中每条边依附的两个顶点都分属于这两个互不相交的子集,两个子集内的顶点不相邻。(简单说就是把一个图的顶点分成两个集合,且集合内的点不邻接)
Here_SDUT
2022/06/29
5.1K0
最全二分图总结(最大匹配、最大权匹配、点覆盖、独立集、路径覆盖,带证明和例题)
hdu----(3118)Arbiter(构造二分图)
Arbiter Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others) Total Submission(s): 800    Accepted Submission(s): 410 Problem Description Arbiter is a kind of starship in the StarCraft science-fiction series. The Arbit
Gxjun
2018/03/22
6400
二分图最大匹配问题(匈牙利算法)
如果一个无向图的的顶点可以分为两个互不相交的子集A和B,那么它就是二分图。也就是说,A、B内部不存在连边,所有连边都一头连着A中的顶点,另一头连着B中的顶点。
灯珑LoGin
2022/10/31
1.1K0
二分图最大匹配问题(匈牙利算法)
二分图判定(图的搜索)
     给定一个具有n个顶点的图。要给图上每个顶点染色,并且要使相邻的顶点颜色不同。问是否能最多用2种颜色进行染色?题目保证没有重边和自环。
砖业洋__
2023/05/06
1800
二分图判定(图的搜索)
HDU 5971 Wrestling Match(二分图染色)
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=5971        题意是有n个人,m个匹配,x个good player,y个bad player,每
Ch_Zaqdt
2019/01/11
4580
判断二分图
如果我们能将一个图的节点集合分割成两个独立的子集A和B,并使图中的每一条边的两个节点一个来自A集合,一个来自B集合,我们就将这个图称为二分图。
你的益达
2020/08/05
3200
HDU 1045 Fire Net(二分图匹配或爆搜)
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1045        题意是有个n*n地图,地图中有空地'.'和墙'X',然后我们要在空地上安置大炮,为
Ch_Zaqdt
2019/01/11
4490
HDU 1084 What Is Your Grade?(排序)
题目在这里:1084 题目描述: “Point, point, life of student!” This is a ballad(歌谣)well known in colleges, an
Enterprise_
2019/02/21
4580
HDU 3488 Tour(拆点+二分图最大权匹配--KM)
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3488        题意是有n个城市,m条边,这个图中有一个或者多个环,问要覆盖所有的点,选那几个环的
Ch_Zaqdt
2019/01/10
6680
相关推荐
二分图详解
更多 >
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档