[二分图最大匹配]hdoj 3729：I'm Telling the Truth

大致题意：

    给出所有学生提供的名次段，判断最多有多少人没说谎，并按照字典序最大的原则输出这些学生编号。

 

大致思路：

    2010年天津赛区匈牙利算法裸题，按照提供的数据建边即可。

 

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int nMax=64;
const int mMax=100005;
const int inf=1<<30;
int low,high;
int map[nMax][mMax];
bool vis[mMax];
int linkk[mMax];

int dfs(int s){
    for(int i=low;i<=high;i++){
        if(!vis[i]&&map[s][i]){
            vis[i]=1;
            if(linkk[i]==-1||dfs(linkk[i])){
                linkk[i]=s;
                return 1;
            }
        }
    }
    return 0;
}

int res[nMax];
int main(){
    int i,j,ans,cas,n,a,b;
    scanf("%d",&cas);
    while(cas--){
        scanf("%d",&n);
        ans=0;
        low=inf;
        high=-1;
        memset(map,0,sizeof(map));
        for(i=1;i<=n;i++){
            scanf("%d%d",&a,&b);
            if(a<low)low=a;
            if(b>high)high=b;
            for(j=a;j<=b;j++){
                map[i][j]=1;
            }
        }
        memset(linkk,-1,sizeof(linkk));
        for(i=n;i>=1;i--){
            memset(vis,0,sizeof(vis));
            if(dfs(i))res[ans++]=i;
        }
        printf("%d\n",ans);
        for(i=ans-1;i>0;i--){
            printf("%d ",res[i]);
        }printf("%d\n",res[0]);
    }
    return 0;
}