hdu3729 I'm Telling the Truth (二分图的最大匹配)

http://acm.hdu.edu.cn/showproblem.php?pid=3729

I‘m Telling the Truth

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1427    Accepted Submission(s): 719

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).

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.

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.

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)

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

Source

2010 Asia Tianjin Regional Contest

Recommend

zhouzeyong

题意:有N(<=60)个人,说了自己的排名在[Ai,Bi]中,(1<=Ai Bi<=10^5),他们说的排名可能冲突,求最多有多少人说实话,并输出字典序最大的说实话的人的编号,编号从1~N。

题解:二分图的最大匹配 匈牙利算法 模板题

贪心只能得到人数,不能得到字典序最大的方案…(贪心的方法:一个一个人来,每次把它放在他说的排名的第一个,如果要放的位置有人,看这个位置的人和我手上的那个人的Bi谁大,把大的拿在手上往后找,重复这样)

所以我们要用二分图最大匹配来搞,可以在kuangbin菊苣这里学习:http://www.cnblogs.com/kuangbin/archive/2012/08/26/2657446.html

由于这题数据有点碉,不能用邻接矩阵,用邻接表比较好。(话说数组实现的邻接表好像叫超碉的链式前向星,我怕了)

代码:

  1 //#pragma comment(linker, "/STACK:102400000,102400000")
  2 #include<cstdio>
  3 #include<cmath>
  4 #include<iostream>
  5 #include<cstring>
  6 #include<algorithm>
  7 #include<cmath>
  8 #include<map>
  9 #include<set>
 10 #include<stack>
 11 #include<queue>
 12 using namespace std;
 13 #define ll long long
 14 #define usll unsigned ll
 15 #define mz(array) memset(array, 0, sizeof(array))
 16 #define mf1(array) memset(array, -1, sizeof(array))
 17 #define minf(array) memset(array, 0x3f, sizeof(array))
 18 #define REP(i,n) for(i=0;i<(n);i++)
 19 #define FOR(i,x,n) for(i=(x);i<=(n);i++)
 20 #define FORD(i,x,n) for(i=(x);i>=(n);i--)
 21 #define RD(x) scanf("%d",&x)
 22 #define RD2(x,y) scanf("%d%d",&x,&y)
 23 #define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z)
 24 #define WN(x) printf("%d\n",x);
 25 #define RE  freopen("D.in","r",stdin)
 26 #define WE  freopen("1biao.out","w",stdout)
 27 #define mp make_pair
 28 #define pb push_back
 29
 30 int N;
 31 int a[111111],b[111111];
 32 vector<int>v;
 33
 34 const int maxu=66;//左点数
 35 const int maxv=111111;//右点数
 36 const int maxm=maxu*maxv;//边数
 37 struct vnode {
 38     int v,next;
 39     int cap;
 40 };
 41 int cnt,head[maxu];
 42 vnode e[maxm];
 43
 44 inline void add(const int &x,const int &y,const int &z) {
 45     e[cnt].v=y;
 46     e[cnt].cap=z;
 47     e[cnt].next=head[x];
 48     head[x]=cnt;
 49     cnt++;
 50 }
 51
 52 int uN,vN;
 53 int linker[maxv];
 54 bool used[maxv];
 55
 56 bool dfs(int u) { //从左边开始找增广路径
 57     int v;
 58     for(v=head[u]; v!=-1; v=e[v].next) {
 59         if(!used[e[v].v]) {
 60             used[e[v].v]=true;
 61             if(linker[e[v].v]==-1||dfs(linker[e[v].v])) {
 62                 linker[e[v].v]=u;
 63                 return true;
 64             }
 65         }
 66     }
 67     return false;//这个不要忘了,经常忘记这句
 68 }
 69
 70 inline void farm() {
 71     int res=0;
 72     int u;
 73     int i,j;
 74     memset(head,-1,sizeof(head));
 75     cnt=0;
 76     vN=100000;
 77     uN=N;
 78     FOR(i,1,uN)
 79     FOR(j,a[i],b[i])
 80     add(i,j,1);
 81     mf1(linker);
 82     for(u=uN; u>=1; u--) {
 83         memset(used,0,sizeof(used));
 84         if(dfs(u)) res++;
 85     }
 86     for(i=1; i<=vN; i++) {
 87         if(linker[i]!=-1) v.pb(linker[i]);
 88     }
 89     return;
 90 }
 91
 92 int main() {
 93     int T;
 94     int i;
 95     scanf("%d",&T);
 96     while(T--) {
 97         scanf("%d",&N);
 98         v.clear();
 99         FOR(i,1,N) {
100             scanf("%d%d",&a[i],&b[i]);
101         }
102         farm();
103         sort(v.begin(),v.end());
104         int maxi=v.size();
105         printf("%d\n",maxi);
106         if(maxi>0)printf("%d",v[0]);
107         FOR(i,1,maxi-1) printf(" %d",v[i]);
108         puts("");
109     }
110     return 0;
111 }

这题是我乱入别的学校在vjudge的训练看到的……过的人最多的题,然后我过不了!尿了,然后发现好像是专题比赛,怕了……

hdu3729 I'm Telling the Truth (二分图的最大匹配)

时间: 08-29

hdu3729 I'm Telling the Truth (二分图的最大匹配)的相关文章

HDU - 3729 I&#39;m Telling the Truth(二分匹配)

题意:有n个人,每个人给出自己的名次区间,问最多有多少个人没撒谎,如果有多解,输出字典序最大的解. 分析: 1.因为字典序最大,所以从后往前分析. 2.假设后面的人没说谎,并将此作为已知条件,然后从后往前依次给每个人找到合适的名次,输出所有能找到合适名次的人即可. 3.假定给第i个人安排名次,第i+1~n个人名次已经安排好,假如第i个人想占的名次被第j个人所占,那就从第j个人可以占的名次中再找个合适的名次给j,然后把空出来的这个名次给i,如果i可以占的所有名次都被占且占领的人找不到其他可以占的名

hdu 3729 I&#39;m Telling the Truth

I'm Telling the Truth Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 1377    Accepted Submission(s): 700 Problem Description After this year’s college-entrance exam, the teacher did a survey in

HDU 3729 I&#39;m Telling the Truth (二分匹配)

题意:给定 n 个人成绩排名区间,然后问你最多有多少人成绩是真实的. 析:真是没想到二分匹配,....后来看到,一下子就明白了,原来是水题,二分匹配,只要把每个人和他对应的区间连起来就好,跑一次二分匹配,裸的. 代码如下: #pragma comment(linker, "/STACK:1024000000,1024000000") #include <cstdio> #include <string> #include <cstdlib> #inc

(转)二分图的最大匹配、完美匹配和匈牙利算法

转载自http://www.renfei.org/blog/bipartite-matching.html 二分图的最大匹配.完美匹配和匈牙利算法 这篇文章讲无权二分图(unweighted bipartite graph)的最大匹配(maximum matching)和完美匹配(perfect matching),以及用于求解匹配的匈牙利算法(Hungarian Algorithm):不讲带权二分图的最佳匹配. 二分图:简单来说,如果图中点可以被分为两组,并且使得所有边都跨越组的边界,则这就是

二分图的最大匹配、完美匹配和匈牙利算法(转)

转载自:http://blog.csdn.net/pi9nc/article/details/11848327 二分图的最大匹配.完美匹配和匈牙利算法 这篇文章讲无权二分图(unweighted bipartite graph)的最大匹配(maximum matching)和完美匹配(perfect matching),以及用于求解匹配的匈牙利算法(Hungarian Algorithm):不讲带权二分图的最佳匹配. 二分图:简单来说,如果图中点可以被分为两组,并且使得所有边都跨越组的边界,则这

二分图与网络流 带权二分图的最大匹配

二分图与网络流  带权二分图的最大匹配 在某书上偶然发现,二分图和网络流是有联系的,在子图u中建立超级源点,在子图v中建立超级汇点,源点到u和汇点到v的每条边容量设为1,u和v中的边的容量也设为1,求出最大流也就是原二分图的最大匹配了. 而求带权二分图的最大匹配也就很容易了,将u和v的权值设为容量,仍然建立超级源点和超级汇点转为网络流解决即可. 真是一切皆可网络流啊...

hdu 2063 过山车(二分图匹配最大匹配数模板)

过山车 Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 10776    Accepted Submission(s): 4748 Problem Description RPG girls今天和大家一起去游乐场玩,终于可以坐上梦寐以求的过山车了.可是,过山车的每一排只有两个座位,而且还有条不成文的规矩,就是每个女生必须找个个男生做par

HDU 2444 The Accomodation of Students 二分图判定+最大匹配

题目来源:HDU 2444 The Accomodation of Students 题意:n个人是否可以分成2组 每组的人不能相互认识 就是二分图判定 可以分成2组 每组选一个2个人认识可以去一个双人间 最多可以有几组 思路:二分图判定+最大匹配 #include <cstdio> #include <cstring> #include <vector> using namespace std; const int maxn = 550; int vis[maxn];

二分图匹配 最大匹配数+最大点覆盖 POJ 1469+POJ 3041

最大匹配数就等于最大点覆盖,因为在图里面,凡是要覆盖的点必定是连通的,而最大匹配之后,若还有点没有覆盖到,则必定有新的匹配,与最大匹配数矛盾,如果去掉一些匹配,则必定有点没有覆盖到. POJ 1469 比较简单,用的经典的二分图匹配算法. ? 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46