POJ 2584 T-Shirt Gumbo （Dinic 或 SAP）

heshao2005

T-Shirt Gumbo Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 2261 Accepted: 1056 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: 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... 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 South Central USA 2003

　　
　　
　　题意：有xn个参赛者,给出每个参赛者所需要的衣服的尺码的大小范围,在该尺码范围内的衣服该选手可以接受,给出这5种型号衣服各自的数量,问是否存在一种分配方案使得每个选手都能够拿到自己尺码范围内的衣服.

思路：最大流 建立超级源点src 与5种衣服相连 边权为衣服的数量 超级汇点与xn个人相连 边权为1 然后每个人与自己相应的尺码间也建立一条边，边权为1 求最大流 等于 xn 就输出  T-shirts rock! 反之 I'd rather not wear a shirt anyway...
　　



#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<map>
using namespace std;
const int VM=1010;
const int EM=500010;
const int INF=0x3f3f3f3f;
struct Edge{
int to,nxt;
int cap;
}edge[EM];
int n,cnt,head[VM],src,des;
int dep[VM];
map<char,int> mp;
void init(){
mp['S']=1;  mp['M']=2;  mp['L']=3;  mp['X']=4;  mp['T']=5;
}
void addedge(int cu,int cv,int cw){
edge[cnt].to=cv;    edge[cnt].cap=cw;   edge[cnt].nxt=head[cu];
head[cu]=cnt++;
edge[cnt].to=cu;    edge[cnt].cap=0;    edge[cnt].nxt=head[cv];
head[cv]=cnt++;
}
int BFS(){
queue<int> q;
while(!q.empty())
q.pop();
memset(dep,-1,sizeof(dep));
dep[src]=0;
q.push(src);
while(!q.empty()){
int u=q.front();
q.pop();
for(int i=head;i!=-1;i=edge.nxt){
int v=edge.to;
if(edge.cap>0 && dep[v]==-1){
dep[v]=dep+1;
q.push(v);
}
}
}
return dep[des]!=-1;
}
int DFS(int u,int minx){
if(u==des)
return minx;
int tmp;
for(int i=head;i!=-1;i=edge.nxt){
int v=edge.to;
if(edge.cap>0 && dep[v]==dep+1 && (tmp=DFS(v,min(minx,edge.cap)))){
edge.cap-=tmp;
edge[i^1].cap+=tmp;
return tmp;
}
}
dep=-1;
return 0;
}
int Dinic(){
int ans=0,tmp;
while(BFS()){
while(1){
tmp=DFS(src,INF);
if(tmp==0)
break;
ans+=tmp;
}
}
return ans;
}
int main(){
//freopen("input.txt","r",stdin);
char s1[20],s2[20],shirt[5];
while(~scanf("%s",s1) && s1[0]!='E'){
cnt=0;
memset(head,-1,sizeof(head));
init();
//printf("s1=%s\n",s1);
cnt=0;
memset(dep,-1,sizeof(dep));
scanf("%d",&n);
//printf("n=%d\n",n);
src=0,  des=n+5+1;
for(int i=1;i<=n;i++){
scanf("%s",shirt);
//printf("------ %s\n",shirt);
            addedge(src,i,INF);
for(int j=mp[shirt[0]];j<=mp[shirt[1]];j++)
addedge(i,n+j,1);
}
int num;
for(int j=n+1;j<=n+5;j++){
scanf("%d",&num);
addedge(j,des,num);
}
scanf("%s",s2);
//printf("s2=%s\n",s2);
int ans=Dinic();
//printf("ans=%d\n",ans);
if(ans>=n)
printf("T-shirts rock!\n");
else
printf("I'd rather not wear a shirt anyway...\n");
}
return 0;
}
　　
　　



#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<map>
using namespace std;
const int VM=210;
const int EM=300010;
const int INF=0x3f3f3f3f;
int N,P,T,cnt,head[VM],src,des;
int dep[VM],gap[VM],cur[VM],aug[VM],pre[VM];
struct Edge{
int frm,to,nxt;
int cap;
}edge[EM<<1],mat[EM<<1];
void addedge(int cu,int cv,int cw){     //无向图时反向边也为cw，有向图则为0
edge[cnt].to=cv;  edge[cnt].cap=cw;  edge[cnt].nxt=head[cu];
head[cu]=cnt++;
edge[cnt].to=cu;  edge[cnt].cap=0;   edge[cnt].nxt=head[cv];
head[cv]=cnt++;
}
void buildgraph(int limit){
cnt=0;
memset(head,-1,sizeof(head));
for(int i=1;i<=P;i++)
if(mat.cap<=limit)
addedge(mat.frm,mat.to,1);
}
int SAP(int n){
int max_flow=0,u=src,v;
int id,mindep;
aug[src]=INF;
pre[src]=-1;
memset(dep,0,sizeof(dep));
memset(gap,0,sizeof(gap));
gap[0]=n;
for(int i=0;i<=n;i++)
cur=head; // 初始化当前弧为第一条弧
while(dep[src]<n){
int flag=0;
if(u==des){
max_flow+=aug[des];
for(v=pre[des];v!=-1;v=pre[v]){     // 路径回溯更新残留网络
id=cur[v];
edge[id].cap-=aug[des];
edge[id^1].cap+=aug[des];
aug[v]-=aug[des];   // 修改可增广量，以后会用到
if(edge[id].cap==0) // 不回退到源点，仅回退到容量为0的弧的弧尾
u=v;
}
}
for(int i=cur;i!=-1;i=edge.nxt){
v=edge.to;    // 从当前弧开始查找允许弧
if(edge.cap>0 && dep==dep[v]+1){  // 找到允许弧
flag=1;
pre[v]=u;
cur=i;
aug[v]=min(aug,edge.cap);
u=v;
break;
}
}
if(!flag){
if(--gap[dep]==0)    // gap优化，层次树出现断层则结束算法
break;
mindep=n;
cur=head;
for(int i=head;i!=-1;i=edge.nxt){
v=edge.to;
if(edge.cap>0 && dep[v]<mindep){
mindep=dep[v];
cur=i;   // 修改标号的同时修改当前弧
                }
}
dep=mindep+1;
gap[dep]++;
if(u!=src)  // 回溯继续寻找允许弧
u=pre;
}
}
return max_flow;
}
int main(){
//freopen("input.txt","r",stdin);
char str[20];
int num;
map<char,int> mp;
mp['S']=1,mp['M']=2,mp['L']=3,mp['X']=4,mp['T']=5;
while(~scanf("%s",str)){
if(strcmp(str,"ENDOFINPUT")==0)
break;
cnt=0;
memset(head,-1,sizeof(head));
scanf("%d",&num);
src=0,  des=num+5+1;
char clo[5];
for(int i=1;i<=num;i++){
scanf("%s",clo);
addedge(src,i,1);
for(int j=mp[clo[0]];j<=mp[clo[1]];j++)
addedge(i,num+j,1);
}
int x;
for(int i=1;i<=5;i++){
scanf("%d",&x);
addedge(num+i,des,x);
}
scanf("%s",str);
if(SAP(des+1)==num)
puts("T-shirts rock!");
else
puts("I'd rather not wear a shirt anyway...");
}
return 0;
}