题目意思是参赛队员要选择队服，队伍的尺寸有5中，S,M,L,X,T
每个人的衣服的尺寸有个接受范围，在这个范围内的衣服都可以接受。
现在每个尺寸的服装有数量限制，但我们要尽可能要让队员拿到服装。
如果每个人都可以拿到符合要求的服装就输出T-shirts rock!
否则就输出I'd rather not wear a shirt anyway...
输入看上去很复杂，先输入start，再输入参赛人员的个数。
然后输入每个人的服装接受范围，再接着输入每种尺寸服装的数量
接下来输入END
输入ENDINPUT结束输入。
这道题目可以用有点像二分图匹配，但二分图匹配是一对一的，这道题目可以说是一对多
但是我们可以做一点处理，用二分图匹配的匈牙利算法思想。
解题思路，将匈牙利算法中cy变成二维，cy【i】【j】表示第i种服装第j件被选走
Numy【i】的值a表示如果第i种服装被选走，那就是第a件被拿走
这是代码中比较关键的地方。
还有一种想法，我还没实现。
因为这道题目的数据比较小，我们可以把每一件衣服都看成独一无二的衣服，这样就变成了一对多的二分图最大匹配。
#include<iostream> #include<cstdio> #include<cstring> #include<functional> #include<algorithm> #define maxn 35 using namespace std; int maps[maxn][maxn];//邻接矩阵 int cy[maxn][maxn];//点集合Y选中情况 int vis[maxn]; int numy[maxn],limit[maxn];//每种衣服的数量 char s[maxn],a,b; int n; int path(int u)//找增广路 { int i,j; for( i=1;i<=5;i++) { if(maps[u][i]&&!vis[i]) { vis[i]=1; if(numy[i]<limit[i])//其实就是匈牙利算法第二个if语句 { cy[i][numy[i]++]=u; return 1; } else//增广 { for( j=0;j<limit[i];j++) if(path(cy[i][j]))//尝试让这件衣服的主人换件衣服 { cy[i][j]=u; return 1; } } } } return 0; } void MulMatch() { int ans=0; memset(cy,0,sizeof(cy)); memset(numy,0,sizeof(numy)); for(int i=1;i<=n;i++) { memset(vis,0,sizeof(vis)); ans+=path(i); } if(ans==n) printf("T-shirts rock!\n"); else printf("I'd rather not wear a shirt anyway...\n"); } int change(char c) { if(c=='S') return 1; else if(c=='M') return 2; else if(c=='L') return 3; else if(c=='X') return 4; else if(c=='T') return 5; } int main() { int i,j; int st,ed; while(scanf("%s",&s)!=EOF) { if(strcmp(s,"ENDOFINPUT")==0) break; scanf("%d",&n); getchar(); memset(maps,0,sizeof(maps)); for(i=1;i<=n;i++) { scanf("%c%c",&a,&b); getchar(); printf("%c %c\n",a,b); st=change(a); ed=change(b); printf("st=%d ed=%d\n",st,ed); for(j=st;j<=ed;j++) maps[i][j]=1; } for(i=1;i<=5;i++) scanf("%d",&limit[i]); scanf("%s",&s); MulMatch(); } return 0; }
