POJ 2584 T-Shirt Gumbo(网络流之最大流）

题目地址：POJ 2584

大水题。。不多说。。上代码

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <ctype.h>
#include <queue>
#include <map>
#include<algorithm>
using namespace std;
const int INF=0x3f3f3f3f;
int head[200], source, sink, nv, cnt, n;
int num[200], d[200], pre[200], cur[200];
int get(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;
}
struct node
{
    int u, v, cap, next;
}edge[10000];
void add(int u, int v, int cap)
{
    edge[cnt].v=v;
    edge[cnt].cap=cap;
    edge[cnt].next=head[u];
    head[u]=cnt++;

    edge[cnt].v=u;
    edge[cnt].cap=0;
    edge[cnt].next=head[v];
    head[v]=cnt++;
}
void bfs()
{
    memset(d,-1,sizeof(d));
    memset(num,0,sizeof(num));
    queue<int>q;
    q.push(sink);
    d[sink]=0;
    num[0]=1;
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        for(int i=head[u];i!=-1;i=edge[i].next)
        {
            int v=edge[i].v;
            if(d[v]==-1)
            {
                d[v]=d[u]+1;
                num[d[v]]++;
                q.push(v);
            }
        }
    }
}
void isap()
{
    memcpy(cur,head,sizeof(cur));
    int flow=0, u=pre[source]=source, i;
    bfs();
    while(d[source]<nv)
    {
        if(u==sink)
        {
            int f=INF, pos;
            for(i=source;i!=sink;i=edge[cur[i]].v)
            {
                if(f>edge[cur[i]].cap)
                {
                    f=edge[cur[i]].cap;
                    pos=i;
                }
            }
            for(i=source;i!=sink;i=edge[cur[i]].v)
            {
                edge[cur[i]].cap-=f;
                edge[cur[i]^1].cap+=f;
            }
            flow+=f;
            u=pos;
        }
        for(i=cur[u];i!=-1;i=edge[i].next)
        {
            if(d[edge[i].v]+1==d[u]&&edge[i].cap)
            {
                break;
            }
        }
        if(i!=-1)
        {
            cur[u]=i;
            pre[edge[i].v]=u;
            u=edge[i].v;
        }
        else
        {
            if(--num[d[u]]==0) break;
            int mind=nv;
            for(i=head[u];i!=-1;i=edge[i].next)
            {
                if(mind>d[edge[i].v]&&edge[i].cap)
                {
                    mind=d[edge[i].v];
                    cur[u]=i;
                }
            }
            d[u]=mind+1;
            num[d[u]]++;
            u=pre[u];
        }
    }
    if(flow==n)
        printf("T-shirts rock!\n");
    else
        printf("I'd rather not wear a shirt anyway...\n");
}
int main()
{
    char s[20], s1[20];
    int i, j, m, x, y, z;
    while(scanf("%s",s)!=EOF)
    {
        if(s[0]=='E')
        {
            break;
        }
        scanf("%d",&n);
        source=0;
        sink=n+5+1;
        nv=sink+1;
        memset(head,-1,sizeof(head));
        cnt=0;
        for(i=1; i<=n; i++)
        {
            scanf("%s",s1);
            add(source,i,1);
            x=get(s1[0]);
            y=get(s1[1]);
            for(j=x;j<=y;j++)
            {
                add(i,j+n,1);
            }
        }
        for(i=1;i<=5;i++)
        {
            scanf("%d",&z);
            add(n+i,sink,z);
        }
        getchar();
        gets(s);
        isap();
    }
    return 0;
}