二分图的最大匹配-hdu-3729-I'm Telling the Truth

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=3729

题目意思：

有n个学生，老师询问每个学生的排名，每个学生都告诉了一个排名区间，求可能的最多的学生说实话的个数，以及那些学生的标号，有相同的则输出字典序最大的。

解题思路：

这题贪心只能求出个数，但要求字典序最大，则须用二分匹配。

将学生标号放到一个集合A里，另外一个集合B放排名。对于每个学生可能在的排名点，建一条边。从学生标号大的开始匹配。

代码

#include<iostream>#include<cmath>#include<cstdio>#include<sstream>#include<cstdlib>#include<string>#include<cstring>#include<algorithm>#include<vector>#include<map>#include<set>#include<stack>#include<list>#include<queue>#include<ctime>#include<bitset>#define eps 1e-6#define INF 0x3f3f3f3f#define PI acos(-1.0)#define ll __int64#define LL long long#define lson l,m,(rt<<1)#define rson m+1,r,(rt<<1)|1#define M 1000000007#pragma comment(linker, "/STACK:1024000000,1024000000")using namespace std;#define Maxn 65#define Maxm 110000int cx[Maxn],cy[Maxm],nx,ny;bool vis[Maxm];vector<int>g[Maxn];int path(int u){    for(int v=0;v<g[u].size();v++)    {        if(!vis[g[u][v]])         {            vis[g[u][v]]=true; //从这个点找，要么找到对应的,要么找不到            if(cy[g[u][v]]==-1||path(cy[g[u][v]]))            {                cy[g[u][v]]=u;                cx[u]=g[u][v];                return 1;            }        }    }    return 0;}int MaxMatch(){    memset(cx,-1,sizeof(cx));    memset(cy,-1,sizeof(cy));    int ans=0;    for(int i=nx;i>=1;i--) //满足字典序最大    {        if(cx[i]==-1)        {            memset(vis,false,sizeof(vis));            ans+=path(i);        }    }    return ans;}int main(){    int t;    scanf("%d",&t);    while(t--)    {        scanf("%d",&nx);        for(int i=1;i<=nx;i++)        {            g[i].clear();            int a,b;            scanf("%d%d",&a,&b);            for(int j=a;j<=b;j++) //将所有的可能排名点建一条边                g[i].push_back(j);        }        int ans=MaxMatch();        printf("%d\n",ans);        for(int i=1;i<=nx;i++)        {            if(cx[i]!=-1)            {                printf("%d",i);                ans--;                if(ans)                    putchar(' ');                else                    putchar('\n');            }        }    }   return 0;}