hdu 3729 I'm Telling the Truth 二分图匹配

裸的二分图匹配。需要输出方案。

#include<cstdio>#include<cstring>#include<vector>#include<algorithm>#include<iostream>using namespace std;#define M 100005#define N 65bool vis[M];vector<int> g[N];int now[M];int n,m;int dfs(int k){    for(int i=0;i<g[k].size();i++)    {        int boy=g[k][i];        if(!vis[boy])        {            vis[boy]=1;            if(now[boy]==0||dfs(now[boy]))            {                now[boy]=k;                return 1;            }        }    }    return 0;}int main(){    int a,b,ans;    int k;    int cas;    scanf("%d",&cas);    while(cas--)    {        scanf("%d",&n);        for(int i=1;i<=n;i++) g[i].clear();        memset(now,0,sizeof(now));        int maxn=0;        for(int i=1;i<=n;i++)        {            scanf("%d%d",&a,&b);            maxn=max(maxn,b);            for(int j=a;j<=b;j++)            g[i].push_back(j);        }        ans=0;        for(int i=n;i>=1;i--)        {            memset(vis,0,sizeof(vis));            ans+=dfs(i);        }        printf("%d\n",ans);        int aa[66];        int top=0;        for(int i=1;i<=maxn;i++)        {            if(now[i])            {                aa[top++]=now[i];            }        }        sort(aa,aa+top);        for(int i=0;i<top;i++)        {            if(i) printf(" %d",aa[i]);            else printf("%d",aa[i]);        }        puts("");    }    return 0;}