首页 > 代码库 > HDU-3729 二分匹配 匈牙利算法

HDU-3729 二分匹配 匈牙利算法

题目大意:学生给出其成绩区间,但可能出现矛盾情况,找出合理组合使没有说谎的人尽可能多,并按maximum lexicographic规则输出组合。

//用学生去和成绩匹配,成绩区间就是学生可以匹配的成绩#include <iostream>#include <queue>#include <vector>#define N 100005using namespace std;struct Node{    int f,t;};Node lis[65];int match[N];int used[N];bool dfs(int now){    //used[now]=1;    for(int i=lis[now].f;i<=lis[now].t;i++)    {        if(!used[i])        {            used[i]=1;            if(match[i]==-1||dfs(match[i]))            {                match[i]=now;                return true;            }        }    }    return false;}void ini(){    fill(used,used+N,0);    fill(match,match+N,-1);}int main(int argc, const char * argv[]) {    cin.sync_with_stdio(false);    int t;    cin>>t;    while(t--)    {        int n;        cin>>n;        for(int i=0;i<n;i++)            cin>>lis[i].f>>lis[i].t;        int ans=0;        ini();        for(int i=n-1;i>=0;i--)//从n向前遍历,保证尽可能得到大的值        {            fill(used,used+N,0);            if(dfs(i))                ans++;        }        cout<<ans<<endl;        priority_queue<int,vector<int>,greater<int> >q;//顺序输出        //int flag=1;        for(int i=N-1;i>=0;i--)            if(match[i]!=-1)                q.push(match[i]+1);        while(!q.empty())        {            if(q.size()!=1)                cout<<q.top()<< ;            else                cout<<q.top()<<endl;            q.pop();        }    }    return 0;}

 

HDU-3729 二分匹配 匈牙利算法