首页 > 代码库 > POJ 2584 T-Shirt Gumbo（二分图最大匹配）
POJ 2584 T-Shirt Gumbo（二分图最大匹配）
题意：
有五种衣服尺码：S,M,L,X,T
N个人，每个人都有一个可以穿的衣服尺码的范围，例：SX，意思是可以穿S,M,L,X的衣服。
给出五种尺码的衣服各有多少件。
如果可以满足所有人的要求，输出 T-shirts rock! 否则输出 I‘d rather not wear a shirt anyway...
样例：
输入：
START 1ST0 0 1 0 0ENDSTART 2SS TT0 0 1 0 0ENDSTART 4SM ML LX XT0 1 1 1 0ENDENDOFINPUT
输出：
T-shirts rock!I‘d rather not wear a shirt anyway...I‘d rather not wear a shirt anyway...
思路：
人数不多，衣服总件数也不多，直接建图，左集合是人，右集合是每一件衣服。二分图最大匹配。看代码。
代码：
char st[105];char Range[25][5];int n;int num[10];int cx[25],cy[205];bool bmask[205];vector<int> graph[25];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,num[5]) cy[i]=-1; rep(i,1,n) if(cx[i]==-1){ mem(bmask,false); ans+=findPath(i); } return ans;}int main(){ map<char,int> mp; mp[‘S‘]=1; mp[‘M‘]=2; mp[‘L‘]=3; mp[‘X‘]=4; mp[‘T‘]=5; while(scanf("%s",st)!=EOF){ if(strcmp(st,"ENDOFINPUT")==0) break; scanf("%d",&n); rep(i,1,n) scanf("%s",Range[i]); num[0]=0; rep(i,1,5){ int x; scanf("%d",&x); num[i]=num[i-1]+x; } scanf("%s",st); rep(i,1,n) graph[i].clear(); rep(i,1,n){ int u=mp[Range[i][0]], v=mp[Range[i][1]]; rep(j,num[u-1]+1,num[v]) graph[i].push_back(j); } int dd=MaxMatch(); if(dd>=n) puts("T-shirts rock!"); else puts("I‘d rather not wear a shirt anyway..."); }}
POJ 2584 T-Shirt Gumbo（二分图最大匹配）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。