本文主要是介绍poj1274 The Perfect Stall (匈牙利算法)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
匈牙利算法模板题目
大牛的blog http://www.byvoid.com/blog/hungary/
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
bool a[205][205];
int mat[205];
bool used[205];
int n,m;
bool crosspath(int k){int i;for(i=1;i<=m;i++){if(!used[i]&&a[k][i]==1){used[i]=1;if(mat[i]==0||crosspath(mat[i])){ //需要理解mat[i]=k;return 1;}}}return 0;
}
int main(){int si,stall;int i,j;while(scanf("%d%d",&n,&m)!=EOF){memset(a,0,sizeof(a));memset(mat,0,sizeof(mat));for(i=1;i<=n;i++){scanf("%d",&si);for(j=1;j<=si;j++){scanf("%d",&stall);a[i][stall]=1;}}int match=0;for(i=1;i<=n;i++){memset(used,0,sizeof(used));if(crosspath(i))match++; //每一次成功的增广路查询都会使匹配加1}printf("%d\n",match);}return 0;
}
另一种图的存储方法
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
bool used[205];
int mat[205];
int n,m;
int a[410][410];
bool crosspath(int k){int i,cur;for(i=1;i<=a[k][0];i++){cur=a[k][i];if(!used[cur]){used[cur]=1;if(mat[cur]==0||crosspath(mat[cur])){mat[cur]=k;return 1;}}}return 0;
}
int main(){int i,j;int si,stall;while(scanf("%d%d",&n,&m)!=EOF){memset(mat,0,sizeof(mat));memset(a,0,sizeof(a));for(i=1;i<=n;i++){scanf("%d",&si);a[i][0]=si;for(j=1;j<=si;j++){scanf("%d",&stall);a[i][j]=stall;}}int ans=0;for(i=1;i<=n;i++){memset(used,0,sizeof(used));if(crosspath(i))ans++;}printf("%d\n",ans);}return 0;
}
这篇关于poj1274 The Perfect Stall (匈牙利算法)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
