首页 > 代码库 > POJ 1274 The Perfect Stall（二分图最大匹配）
POJ 1274 The Perfect Stall（二分图最大匹配）
题意：
N头牛M个牛棚，每只牛都有它自己指定的若干个它愿意呆的牛棚。
每个牛棚最多呆一头牛。
问最多可以满足多少头牛的愿望。
思路：
裸二分图最大匹配。
代码：
int n,m;vector<int> graph[205];int cx[205],cy[205];bool bmask[205];int findPath(int u){ int L=graph[u].size(); rep(i,0,L-1){ int v=graph[u][i]; if(!bmask[v]){ bmask[v]=true; if(cy[v]==-1||findPath(cy[v])){ cy[v]=u; cx[u]=v; return 1; } } } return 0;}int MaxMatch(){ int ans=0; rep(i,1,n) cx[i]=-1; rep(i,1,m) cy[i]=-1; rep(i,1,n) if(cx[i]==-1){ mem(bmask,false); ans+=findPath(i); } return ans;}int main(){ while(scanf("%d%d",&n,&m)!=EOF){ rep(i,1,n) graph[i].clear(); rep(i,1,n){ int x,tx; scanf("%d",&x); while(x--){ scanf("%d",&tx); graph[i].push_back(tx); } } int dd=MaxMatch(); printf("%d\n",dd); }}
POJ 1274 The Perfect Stall（二分图最大匹配）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。