首页 > 代码库 > hdu3729 I'm Telling the Truth （二分图的最大匹配）
hdu3729 I'm Telling the Truth （二分图的最大匹配）
http://acm.hdu.edu.cn/showproblem.php?pid=3729
I‘m Telling the TruthTime 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 245004 50055005 50065004 50065004 500674 52 31 22 24 42 33 4 Sample Output 32 3 451 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 （二分图的最大匹配）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。