題目大意：學生給出其成績區間，但可能出現矛盾情況，找出合理組合使沒有說謊的人盡可能多，并按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()<<' ';elsecout<<q.top()<<endl;q.pop();}}return 0; }

?

轉載于:https://www.cnblogs.com/LukeStepByStep/p/5813061.html

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的HDU-3729 二分匹配 匈牙利算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。