最大匹配(模板题) pku1274 && pku 1469&& pku 2239&&hdu2063

it2022-05-06  4

关于二分匹配,一开始总下不了手,应该说,不知道该从何下手,课件上就很直接的就引入匈牙利算法,看了好久之后还是一样一头雾水,这让我情何以堪啊!!

不过,跟这算法走一遍之后,感觉有些许的理解这个算法了,问题的关键在与寻找增广路径,当图中不存在增广路径时,表明已经是最大匹配了

这里面的四道题目,有三道是完全的模板题,pku2239需要稍微转换一下,题目中说,在course和每周的12个教室进行匹配,不发生冲突,其实也就是总共300个courses和7*12个教室进行匹配,只需要在输入的时候稍微的修改一下,a 表示course,q days 在p class上课,即表示在mat[a][12*(p-1)+q]=1 

pku 1274 #include<iostream>#include<string>#define MAXN 210using namespace std;bool mat[MAXN][MAXN],vis[MAXN];int match[MAXN],vn,vm;int path(int s){for(int i=1;i<=vm;i++)if(mat[s][i]&&!vis[i]) { vis[i]=true;if(match[i]==-1||path(match[i])) { match[i]=s;return 1; } }return 0;}int main(){int k,m,a;while(scanf("%d %d",&vn,&vm)==2) { memset(match,-1,sizeof(match)); memset(mat,false,sizeof(mat));for(int i=1;i<=vn;i++) { scanf("%d",&m);for(int j=1;j<=m;j++) { scanf("%d",&a); mat[i][a]=true; } }int ans=0;for(int i=1;i<=vn;i++) { memset(vis,0,sizeof(vis)); ans+=path(i); } printf("%d\n",ans); }return 0;}

  

pku 1469 #include<iostream>#include<string>#define MAXN 310using namespace std;bool mat[110][MAXN],vis[MAXN];int match[MAXN],vn,vm;int path(int s){for(int i=1;i<=vm;i++)if(mat[s][i]&&!vis[i]) { vis[i]=true;if(match[i]==-1||path(match[i])) { match[i]=s;return 1; } }return 0;}int main(){int m,a,cas; scanf("%d",&cas);while(cas--) { scanf("%d %d",&vn,&vm); memset(match,-1,sizeof(match)); memset(mat,false,sizeof(mat));for(int i=1;i<=vn;i++) { scanf("%d",&m);for(int j=1;j<=m;j++) { scanf("%d",&a); mat[i][a]=true; } }int ans=0;for(int i=1;i<=vn;i++) { memset(vis,0,sizeof(vis)); ans+=path(i); }if(ans==vn) printf("YES\n");else printf("NO\n"); }return 0;}

  

pku 2239 #include<iostream>#include<string>#include<algorithm>using namespace std;bool mat[301][12*8],vis[12*8];int match[12*8],n;int path(int s){for(int i=1;i<=12*7+1;i++)if(mat[s][i]&&!vis[i]) { vis[i]=true;if(match[i]==-1||path(match[i])) { match[i]=s;return 1; } }return 0;}int main(){int t,a,b;while(scanf("%d",&n)==1) { memset(mat,false,sizeof(mat)); memset(match,-1,sizeof(match));for(int i=1;i<=n;i++) { scanf("%d",&t);while(t--) { scanf("%d %d",&a,&b); mat[i][(a-1)*12+b]=1; } }int ans=0;for(int i=1;i<=n;i++) { memset(vis,false,sizeof(vis)); ans+=path(i); } printf("%d\n",ans); }return 0;}

  

hdu 2063 #include<iostream>#define MAXN 501using namespace std;int vn,vm,mat[MAXN][MAXN],match[MAXN];bool vis[MAXN];int path(int s){for(int i=1;i<=vn;i++) {if(mat[s][i]&&!vis[i]) { vis[i]=true;if(match[i]==-1|| path(match[i])) { match[i]=s;return 1; } } }return 0;}int main(){int k,a,b;while(scanf("%d",&k)==1&&k) { scanf("%d %d",&vm,&vn); memset(mat,0,sizeof(mat));for(int i=0;i<k;i++) { scanf("%d %d",&a,&b); mat[a][b]=1; }int ans=0; memset(match,-1,sizeof(match));for(int i=1;i<=vm;i++) { memset(vis,false,sizeof(vis)); ans+=path(i); } printf("%d\n",ans); }return 0;}

  

转载于:https://www.cnblogs.com/nanke/archive/2011/08/22/2149928.html

相关资源:DirectX修复工具V4.0增强版

最新回复(0)