POJ 2584 T-Shirt Gumbo 最大流和多重匹配
周阳波
T-Shirt Gumbo
| Time Limit: 1000MS | Memory Limit: 65536K | |
| Total Submissions: 2488 | Accepted: 1158 |
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
A single data set has 4 components:
- Start line - A single line:
START X
where (1 <= X <= 20) is the number of contestants demanding shirts.
- Tolerance line - A single line containing X space-separated pairs of letters indicating the size tolerances of each contestant. Valid size letters are S - small, M - medium, L - large, X - extra large, T - extra extra large. Each letter pair will indicate the range of sizes that will satisfy a particular contestant. The pair will begin with the smallest size the contestant will accept and end with the largest. For example:
MX
would indicate a contestant that would accept a medium, large, or extra large T-shirt. If a contestant is very picky, both letters in the pair may be the same.
- Inventory line - A single line:
S M L X T
indicating the number of each size shirt in Boudreaux and Thibodeaux's inventory. These values will be between 0 and 20 inclusive.
- End line - A single line:
END
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...
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
给你5种型号衣服的每种型号的数量，然后有n个人，每个人能够穿的型号有一个范围，让你求能否使得所有人都得到自己满意的衣服。
此题有两种解法，一种是最大流来解，一种用二分匹配来解。
用最大流来解的话，这样建图：
源点和每个学生连接，容量为1
学生和适合的衣服型号连边，容量为1
衣服的型号和汇点连边，容量为这件型号衣服的数量
//432K 0MS
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define inf 9999999
#define M 1007
#define MIN(a,b) a>b?b:a;
using namespace std;
struct E
{
int v,w,next;
}edg[500000];
int dis[2000],gap[2000],head[2000],nodes;
char s[M],shirt[M][2];
int num[M];
int sourse,sink,nn;
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;
}
void addedge(int u,int v,int w)
{
edg[nodes].v=v;
edg[nodes].w=w;
edg[nodes].next=head[u];
head[u]=nodes++;
edg[nodes].v=u;
edg[nodes].w=0;
edg[nodes].next=head[v];
head[v]=nodes++;
}
int dfs(int src,int aug)
{
if(src==sink)return aug;
int left=aug,mindis=nn;
for(int j=head[src];j!=-1;j=edg[j].next)
{
int v=edg[j].v;
if(edg[j].w)
{
if(dis[v]+1==dis[src])
{
int minn=MIN(left,edg[j].w);
minn=dfs(v,minn);
edg[j].w-=minn;
edg[j^1].w+=minn;
left-=minn;
if(dis[sourse]>=nn)return aug-left;
if(left==0)break;
}
if(dis[v]<mindis)
mindis=dis[v];
}
}
if(left==aug)
{
if(!(--gap[dis[src]]))dis[sourse]=nn;
dis[src]=mindis+1;
gap[dis[src]]++;
}
return aug-left;
}
int sap(int s,int e)
{
int ans=0;
nn=e+1;
memset(dis,0,sizeof(dis));
memset(gap,0,sizeof(gap));
gap[0]=nn;
sourse=s;
sink=e;
while(dis[sourse]<nn)
ans+=dfs(sourse,inf);
return ans;
}
int main()
{
while(scanf("%s",s)&&strcmp(s,"ENDOFINPUT")!=0)
{
int n,t;
memset(head,-1,sizeof(head));
nodes=0;
scanf("%d",&n);
for(int i=1; i<=n; i++)
{
addedge(0,i,1);
scanf("%s",shirt[i]);
}
t=n+6;
for(int i=1; i<=5; i++)
{
scanf("%d",&num[i]);
addedge(i+n,t,num[i]);
}
scanf("%s",s);
for(int i=1; i<=n; i++)
{
int id1=judge1(i),id2=judge2(i);
for(int j=id1;j<=id2;j++)
addedge(i,j+n,1);
}
int ans=sap(0,t);
if(ans==n)printf("T-shirts rock!\n");
else printf("I'd rather not wear a shirt anyway...\n");
}
return 0;
}
用二分匹配的话，将所有的衣服编号，将每个人适合的衣服连边，最后求最大匹配。
//1404K 0MS
#include<stdio.h>
#include<string.h>
#include<math.h>
#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;
}
类似资料：