题目地址：HDU 3729
二分图最大匹配+按字典序输出结果。只要从数字大的开始匹配就可以保证字典序最大了。群里有人问。。就顺手写了这题。。
代码如下：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int vis[110000], head[110000], cnt, link[110000], n, a[70], tot;
struct node
{
int u, v, next;
}edge[1000000];
void add(int u, int v)
{
edge[cnt].v=v;
edge[cnt].next=head[u];
head[u]=cnt++;
}
int dfs(int u)
{
int i;
for(i=head[u];i!=-1;i=edge[i].next)
{
int v=edge[i].v;
if(!vis[v])
{
vis[v]=1;
if(link[v]==-1||dfs(link[v]))
{
link[v]=u;
return 1;
}
}
}
return 0;
}
void hungary()
{
int i, ans=0;
memset(link,-1,sizeof(link));
for(i=n;i>=1;i--)
{
memset(vis,0,sizeof(vis));
if(dfs(i))
{
a[ans++]=i;
}
}
printf("%d\n",ans);
sort(a,a+ans);
for(i=0;i<ans-1;i++)
{
printf("%d ",a[i]);
}
printf("%d\n",a[ans-1]);
}
int main()
{
int t, i, j, l, r;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
memset(head,-1,sizeof(head));
cnt=0;
tot=0;
for(i=1;i<=n;i++)
{
scanf("%d%d",&l,&r);
for(j=l;j<=r;j++)
{
add(i,j);
}
}
hungary();
}
return 0;
}
HDU 3729 I'm Telling the Truth(二分图最大匹配+结果输出）,布布扣,bubuko.com
HDU 3729 I'm Telling the Truth(二分图最大匹配+结果输出）
原文：http://blog.csdn.net/scf0920/article/details/38321859