# 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

```  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 };
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;
49     cnt++;
50 }
51
52 int uN,vN;
54 bool used[maxv];
55
56 bool dfs(int u) { //从左边开始找增广路径
57     int v;
59         if(!used[e[v].v]) {
60             used[e[v].v]=true;
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;
75     cnt=0;
76     vN=100000;
77     uN=N;
78     FOR(i,1,uN)
79     FOR(j,a[i],b[i])
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++) {
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 }```

hdu3729 I'm Telling the Truth （二分图的最大匹配）

## 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