首页 > 代码库 > hdu 3729
hdu 3729
二分图匹配,应该叫匈牙利算法,以前做过这种题,看明白了思想,板子忘了,无奈只能看白书上的板子,这个板子有点乱,比如1,2,3匹配1,2,3就会乱匹配,建议还是去网上学学好的板子,这里我用x和N+X区分了匹配项
#include <iostream> #include <cstring> #include <cstdio> #include <algorithm> #include <vector> using namespace std; const int maxn=100000+10; vector<int> G[2*maxn]; int match[maxn*2]; bool used[maxn*2]; int n,t; bool dfs(int v) { used[v]=true; for(int i=0;i<G[v].size();i++) { int u=G[v][i],w=match[u]; if(w<0||!used[w]&&dfs(w)) { match[u]=v; match[v]=u; return true; } } return false; } int main() { scanf("%d",&t); while(t--) { for(int i=1;i<=n;i++) G[i].clear(); scanf("%d",&n); for(int i=1;i<=n;i++) { int a,b; scanf("%d%d",&a,&b); a=100000+a;//区分匹配项 b=100000+b; for(int j=a;j<=b;j++) { G[i].push_back(j); G[j].push_back(i); } } int res=0; int cc[70]; memset(match,-1,sizeof(match)); for(int i=n;i>=1;i--) { if(match[i]<0) { memset(used,0,sizeof(used)); if(dfs(i)) { cc[res]=i; res++; } } } sort(cc,cc+res); printf("%d\n",res); for(int i=0;i<res;i++) { if(i) printf(" "); printf("%d",cc[i]); } printf("\n"); } return 0; }
hdu 3729
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。