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

[二分图最大匹配]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;}