用二分匹配的话，将所有的衣服编号，将每个人适合的衣服连边，最后求最大匹配。
//1404K 0MS
#include
#include
#include
#define M 507 #define inf 0x3f3f3f int link[M],g[M][M],f[M][2]; bool vis[M]; int num[M]; int n,m; char s[27],shirt[M][2]; int judge1(int x) { if(shirt[x][0]=='S')return 1; if(shirt[x][0]=='M')return 2; if(shirt[x][0]=='L')return 3; if(shirt[x][0]=='X')return 4; if(shirt[x][0]=='T')return 5; } int judge2(int x) { if(shirt[x][1]=='S')return 1; if(shirt[x][1]=='M')return 2; if(shirt[x][1]=='L')return 3; if(shirt[x][1]=='X')return 4; if(shirt[x][1]=='T')return 5; } bool find(int i) { for(int j=1;j<=m;j++) if(!vis[j]&&g[i][j]) { vis[j]=true; if(!link[j]||find(link[j])) { link[j]=i; return true; } } return false; } int main() { while(scanf("%s",s)&&strcmp(s,"ENDOFINPUT")!=0) { memset(g,0,sizeof(g)); memset(link,0,sizeof(link)); scanf("%d",&n); for(int i=1; i<=n; i++) scanf("%s",shirt[i]); int sum=0; for(int i=1;i<=5;i++) { scanf("%d",&num[i]); if(num[i]) { f[i][0]=sum+1; sum+=num[i]; f[i][1]=sum; } else f[i][0]=-1; } m=sum; scanf("%s",s); for(int i=1; i<=n; i++) { int id1=judge1(i),id2=judge2(i); for(int j=id1;j<=id2;j++) { if(f[j][0]==-1)continue; for(int k=f[j][0];k<=f[j][1];k++) g[i][k]=1; } } int ans=0; for(int i=1;i<=n;i++) { memset(vis,false,sizeof(vis)); if(find(i))ans++; } if(ans==n)printf("T-shirts rock!\n"); else printf("I'd rather not wear a shirt anyway...\n"); } return 0; }