一个点集是学生,一个点集是排名。然后通过学生的排名范围连线,求此二分图的最大匹配。

本题还要求是最大字典序输出,那么由贪心可得,你让标号从大到小找增广边就行了。

#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <fstream>
#include <iostream> #define rep(i, l, r) for(int i=l; i<=r; i++)
#define down(i, l, r) for(int i=l; i>=r; i--)
#define N 69
#define M 100009 using namespace std;
int read()
{
int x=0, f=1; char ch=getchar();
while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
return x*f;
} int n, l[N], r[N], k[M], b[M], ans, ansk[N], s; bool Find(int x)
{
rep(i, l[x], r[x]) if (b[i]!=s)
{
b[i]=s; if (!k[i] || Find(k[i])) { k[i]=x; return true; }
}
return false;
} int main()
{
int t=read(); while (t--)
{
n=read();
rep(i, 1, n) l[i]=read(), r[i]=read();
rep(i, 1, M-1) k[i]=b[i]=0;
rep(i, 1, n) ansk[i]=0; ans=0;
down(i, n, 1) if (Find(s=i)) ans++, ansk[i]=1;
printf("%d\n", ans);
rep(i, 1, n) if (ansk[i]) { if (--ans) printf("%d ", i); else printf("%d\n", i); }
}
return 0;
}

  

最新文章

  1. ABP源码分析四十六:ABP ZERO中的Ldap模块
  2. 【重点】Shell入门教程:流程控制(2)条件判断的写法
  3. algorithm 学习之 for_each
  4. HEX文件格式和其校验算法
  5. WEB 业务测试中需要关注的问题
  6. 第二天 django apache
  7. 数据结构Java实现03----单向链表的插入和删除
  8. SQLServer Note
  9. Oracle无法启动,ORA-01034、ORA-01078
  10. 4-Highcharts曲线图之时间轴折线图
  11. Linux 总结1
  12. UVA 11762 Race to 1(记忆化+期望)
  13. Redhat Enterprise Linux中如何关闭SELinux?
  14. iOS多线程——同步异步串行并行
  15. JS基础(二)
  16. win 常用CMD命令备忘
  17. IntelliJ Idea更新jsp文件后浏览器端不更新的问题
  18. Android VLC播放器二次开发3——音乐播放(歌曲列表+歌词同步滚动)
  19. canvas移动端兼容性问题总结
  20. Haskell语言学习笔记(72)Free Monad

热门文章

  1. Cocos2d-x——导入Cocostudio资源
  2. CoreData介绍
  3. 【PowerShell语音计算器】
  4. python 遍历list
  5. mac 使用homebrew 安装mysql
  6. 洛谷 P5015 标题统计
  7. destoon 数据库操作
  8. 将php数组转js数组,js如何接收PHP数组,json的用法
  9. Ubuntu 16.04中安装谷歌Chrome浏览器
  10. python爬虫基础15-python图像处理,PIL库