首页 > 代码库 > POJ2584_T-Shirt Gumbo(二分图多重最大匹配/最大流)
POJ2584_T-Shirt Gumbo(二分图多重最大匹配/最大流)
解题报告
http://blog.csdn.net/juncoder/article/details/38239367
题目传送门
题意：
X个參赛选手，每一个选手有衣服大小的范围，5种大小的队服，求能否使每一个选手都拿到符合自己大小范围的衣服。
思路：
X人5种衣服，有的人选的衣服可能大小一样，这样就是二分图的多重最大匹配。源点到5种衣服的容量就是衣服的数量。
#include <queue>
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define inf 99999999
using namespace std;
int n,mmap[30][30],m,l[30],t;
int T_shirt[30];
int bfs()
{
queue<int >Q;
Q.push(0);
memset(l,-1,sizeof(l));
l[0]=0;
while(!Q.empty()) {
int u=Q.front();
Q.pop();
for(int i=0; i<=m; i++) {
if(l[i]==-1&&mmap[u][i]) {
l[i]=l[u]+1;
Q.push(i);
}
}
}
if(l[m]>1)return 1;
else return 0;
}
int dfs(int x,int f)
{
int a;
if(x==m)return f;
for(int i=0; i<=m; i++) {
if(mmap[x][i]&&l[i]==l[x]+1&&(a=dfs(i,min(f,mmap[x][i])))) {
mmap[x][i]-=a;
mmap[i][x]+=a;
return a;
}
}
l[x]=-1;
return 0;
}
int main()
{
int i,j;
char str[100];
char s[10];
T_shirt['S'-'A']=1;
T_shirt['M'-'A']=2;
T_shirt['L'-'A']=3;
T_shirt['X'-'A']=4;
T_shirt['T'-'A']=5;
while(cin>>str) {
memset(mmap,0,sizeof(mmap));
if(!strcmp(str,"ENDOFINPUT"))
break;
if(!strcmp(str,"END"))
continue;
cin>>n;
m=n+5+1;
for(i=1; i<=n; i++) {
cin>>s;
int a=T_shirt[s[0]-'A'];
int b=T_shirt[s[1]-'A'];
if(a>b)
swap(a,b);
for(j=a; j<=b; j++) {
mmap[j][i+5]=1;
}
mmap[i+5][m]=1;
}
for(i=1; i<=5; i++) {
scanf("%d",&t);
mmap[0][i]=t;
}
int ans=0;
cin>>str;
while(bfs())
while(t=dfs(0,inf))
ans+=t;
if(ans==n)
cout<<"T-shirts rock!"<<endl;
else cout<<"I'd rather not wear a shirt anyway..."<<endl;
if(!strcmp(str,"END"))continue;
}
return 0;
}
T-Shirt Gumbo
Description Boudreaux and Thibodeaux are student volunteers for this year‘s ACM South Central Region‘s programming contest. One of their duties is to distribute the contest T-shirts to arriving teams. The T-shirts had to be ordered in advance using an educated guess as to how many shirts of each size should be needed. Now it falls to Boudreaux and Thibodeaux to determine if they can hand out T-shirts to all the contestants in a way that makes everyone happy. Input Input to this problem will consist of a (non-empty) series of up to 100 data sets. Each data set will be formatted according to the following description, and there will be no blank lines separating data sets. A single data set has 4 components:
After the last data set, there will be a single line: ENDOFINPUT Output For each data set, there will be exactly one line of output. This line will reflect the attitude of the contestants after the T-shirts are distributed. If all the contestants were satisfied, output: T-shirts rock! Otherwise, output: I‘d rather not wear a shirt anyway... Sample Input START 1 ST 0 0 1 0 0 END START 2 SS TT 0 0 1 0 0 END START 4 SM ML LX XT 0 1 1 1 0 END ENDOFINPUT Sample Output T-shirts rock! I‘d rather not wear a shirt anyway... I‘d rather not wear a shirt anyway... Source field=source&key=South+Central+USA+2003" style="text-decoration:none">South Central USA 2003 |
POJ2584_T-Shirt Gumbo(二分图多重最大匹配/最大流)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。