題目鏈接：http://acm.hdu.edu.cn/showproblem.php?pid=3729

解題思路：節(jié)點(diǎn)i對(duì)Xi~Yi之間的每一個(gè)點(diǎn)都連一條邊，這樣問(wèn)題就轉(zhuǎn)化成二分圖的最大匹配了。字典序最大，這里可以根據(jù)匈牙利算法的特點(diǎn)，從n枚舉到1即可。

#include<iostream> #include<cstdio> #include<cstring> using namespace std;const int maxn = 100005; struct node {int x,y; }a[105]; int n,m,g[65][maxn]; int match[maxn],res[65]; bool vis[maxn];bool dfs(int u) {for(int i = a[u].x; i <= a[u].y; i++){if(vis[i] == false){vis[i] = true;if(match[i] == -1 || dfs(match[i])){match[i] = u;res[u] = 1;return true;}}}return false; }void Max_Match() {int ans = 0;memset(match,-1,sizeof(match));memset(res,-1,sizeof(res));for(int i = n; i >= 1; i--){memset(vis,false,sizeof(vis));if(dfs(i)) ans++;}printf("%d\n",ans);for(int i = 1,cnt = 0; i <= n; i++)if(res[i] == 1){cnt++;if(cnt == ans) printf("%d\n",i);else printf("%d ",i);} }int main() {int t;scanf("%d",&t);while(t--){scanf("%d",&n);for(int i = 1; i <= n; i++)scanf("%d%d",&a[i].x,&a[i].y);Max_Match();}return 0; }

總結(jié)

以上是生活随笔為你收集整理的hdu 3729(二分图最大匹配+最大字典序)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。