POJ2584题目链接
题目大意：//题目大意：
若干个人需要衣服 能接受的衣服尺寸大小范围给出
但是各个尺寸的衣服数量给定上限 求是否能满足所有人都有衣服
分析 ： 如果没有给定衣服个数 那么就是一个裸的二分图匹配
但是现在给定了匹配对象的限定值 需要用到二分图的多重匹配
题目分析：
//分析下 匈牙利算法板子
/*
有俩层判断 一层是判断是否存在路径map 和当前节点查找时是否访问该对象vis
二层是判断是否该查找对象是否存在前驱 假如有前驱，则对应前驱是否用dfs能找到额外的对象 即更新状态
在这里 只是把第二层判断拆开
一是：是否存在前驱改为是否数量还剩 剩下说明还能分配 相当于没有前驱
二是：如果数量不够，那么对该对象即cnt进行遍历 即把这个型号衣服的所有前驱全部dfs重新查找相比较 只是判断和查询更改次数变多了，所以用数组来存储，用for来遍历
#include<iostream>
#include<cstring>
using namespace std;
int n,map[105][105];
int flag[105][105];
int vis[105];
int num[10];
int cnt[10];
int box(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;elsereturn -1;
}
int dfs(int x)
{ for(int i=1;i<=5;i++){if(vis[i]==0&&map[x][i]){vis[i]=1;if(cnt[i]<num[i])//判断是否现在已经使用了的 小于上限 是的话就找到了 {//二维数组记录前驱 flag[i][++cnt[i]] =x;return 1;}else//当前衣服没有了 那么查找交替路{for(int j=1;j<=cnt[i];j++){if(dfs(flag[i][j])){flag[i][j] =x;return 1;}}} }}return 0;
}
int main()
{char s[15]; while(scanf("%s",&s)!=EOF){if(strcmp(s,"ENDOFINPUT")==0)break;scanf("%d",&n);memset(map,0,sizeof(map));memset(cnt,0,sizeof(cnt));memset(flag,0,sizeof(flag));
// memset()for(int i=1;i<=n;i++){scanf("%s",s);int low = box(s[0]);int top = box(s[1]);//衣服大小范围的上下限for(int j=low;j<=top;j++)map[i][j] = 1; }for(int i=1;i<=5;i++)scanf("%d",&num[i]);scanf("%s",s);int ans=0;for(int i=1;i<=n;i++){memset(vis,0,sizeof(vis));if(dfs(i))ans++;}if(ans==n)printf("T-shirts rock!\n");elseprintf("I'd rather not wear a shirt anyway...\n");}
}