POJ 2584 T-Shirt Gumbo 最大流和多重匹配

Description

Input

Output

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

//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;
}