http://acm.hdu.edu.cn/showproblem.php?pid=3729
不看解析 还真不敢用匈牙利算法解 怕超时
后来想想 在用人找对应点的时候 对应点的范围宽的话 搜的广度会增加 但深度会减少 对应点的范围窄的话 深度会增加 但广度会减少
所以总体来说时间复杂度不高
应为要字典序最大的结果 所以要从编号大的人开始搜
代码：
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<vector>
#include<set>
#include<queue>
#include<map>
#include<string>
#include <iomanip>
using namespace std;
const int N=100;
const int M=100005;
struct node
{
int l,r;
}mem[N];
int f[M];
bool visited[M];
vector<int>ans;
bool dfs(int x)
{
for(int i=mem[x].l;i<=mem[x].r;++i)
{
if(!visited[i])
{
visited[i]=true;
if(f[i]==-1||dfs(f[i]))
{
f[i]=x;
return true;
}
}
}
return false;
}
int main()
{
//freopen("data.txt","r",stdin);
int T;
scanf("%d",&T);
while(T--)
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;++i)
{
scanf("%d %d",&mem[i].l,&mem[i].r);
}
ans.clear();
memset(f,-1,sizeof(f));
for(int i=n;i>=1;--i)
{
memset(visited,false,sizeof(visited));
dfs(i);
}
for(int i=1;i<M;++i)
if(f[i]!=-1)
ans.push_back(f[i]);
printf("%d\n",ans.size());
sort(ans.begin(),ans.end());
for(unsigned int i=0;i<ans.size();++i)
{
if(i)
printf(" ");
printf("%d",ans[i]);
}
printf("\n");
}
return 0;
}