首页 > 代码库 > 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 二分匹配 匈牙利算法
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。