HDU 3729 二分匹配反向匹配

题意：

给定 n个学生说的自己考试排名的可能范围

确定最多几个人说真话

如果有多种答案，输出字典序最大的那种( 要求字典序最大，所以solve中从最大字典序开始匹配)

思路：

题目给定点映射到数轴的区间上，问最多多少点可以成功映射到数轴上

很显然点就是 x集，整个数轴就是 y集，点对应的整个区间就是映射的边，所以直接有了一个二分图

#include<iostream>  
#include<string.h>  
#include<stdio.h>  
using namespace std;  
  
#define N 100100  
#define M 65  
struct node{  
    int x,y;  
}len[M];  
int n;  
  
int lef[N],match[M];  
bool vis[N];  
bool dfs(int x){  
  
    for(int i=len[x].x; i<= len[x].y; i++){  
        if(!vis[i])  
        {  
            vis[i] = true;  
            if(lef[i] == -1 || dfs(lef[i])) {  
                lef[i] = x;  
                match[x] = i;  
                return true;  
            }  
        }  
    }  
    return false;  
}  
int solve(){  
    memset(lef, -1, sizeof(lef));  
    memset(match,-1,sizeof(match));  
    int ans = 0;  
    for(int i = n-1 ; i >= 0; i-- ){  
        memset(vis,0,sizeof(vis));  
        ans += dfs(i);  
    }  
    return ans;  
}  
int main(){  
    int i,T;scanf("%d",&T);  
    while(T--){  
        scanf("%d",&n);  
        for(i=0;i<n;i++)scanf("%d %d",&len[i].x,&len[i].y);  
        int ans = solve();  
        printf("%d\n",ans);  
        for(i=0;i<n;i++)  
            if(match[i] != -1){  
                ans--;  
                printf("%d",i+1);  
                if(ans)printf(" ");  
                else   printf("\n");  
            }  
  
    }  
    return 0;  
}

补充：软件开发 , C++ ,

HDU 3729 二分匹配 反向匹配

HDU 3729 二分匹配反向匹配