UVa 11045 My T-shirt suits me [Flow]

11045    My T-shirt suit...    poao899    Accepted    C++    0.020    2009-12-12 05:59:59                      .


花了半小時co

不過少打一個括號debug半小時= =


是說  同TIOJ 1469 制服發放問題

不過貌似有其他解法= =看TIOJ大家的速度...還有code length

應該是有辦法greedy?

//******************************

//13:04 - 13:31
#include<stdio.h>
#include<string.h>
#define MAX 1000
#define INF 100000
struct arc{
    int j,con;
    arc *topair,*next;
    void set(int to,int c,arc *t,arc *n){
        j=to;con=c;
        topair=t;next=n;
    }
}A[MAX],*N[MAX],*from[MAX];
int arr[INF],t;
struct queue{
    int front,rear,*ar;
    void init(){
        front=rear=0;
        ar=arr;
    }
    int deq(){
        int a=ar[front];
        front=++front%INF;
        return a;
    }
    void enq(int a){
        ar[rear]=a;
        rear=++rear%INF;
    }
}q;
int arcCnt,n,m,max,fa[MAX];
char s[10];
arc* get(){
    return A+arcCnt++;
}
void build(int i,int j,int c){
    arc *p=get(),*q=get(),*r;
    r=N[i];
    N[i]=p;
    p->set(j,c,q,r);
    r=N[j];
    N[j]=q;
    q->set(i,0,p,r);
}
/*
S 0
T MAX-1
size
XXL - XS    201 - 206
*/
main(){
    scanf("%d",&t);
    while(t--){
        scanf("%d%d\n",&n,&m);
        //Initialize
        arcCnt=max=0;
        for(int i=0;i<MAX;i++){
            A[i].topair=A[i].next=N[i]=NULL;
        }
        // S & T
        n/=6;
        for(int i=201;i<207;i++)
            build(0,i,n);
        //Input
        for(int i=1;i<=m;i++){
            int toSet;
            for(int j=0;j<2;j++){
                scanf("%s",s);
                if(s[0]=='X'){
                    if(s[1]=='X')
                        toSet=201;
                    else if(s[1]=='L')
                        toSet=202;
                    else if(s[1]=='S')
                        toSet=206;
                }
                else{
                    switch(s[0]){
                        case'L':
                            toSet=203;
                            break;
                        case'M':
                            toSet=204;
                            break;
                        case'S':
                            toSet=205;
                            break;
                    }
                }
                build(toSet,i,1);
            }
            build(i,999,1);
        }
        //Max-Flow
        while(1){
            int flow=INF;
            //Initialize
            for(int i=0;i<MAX;i++){
                fa[i]=-1;
                from[i]=NULL;
            }
            q.init();
            q.enq(0);
            //BFS
            while(q.front!=q.rear){
                int now=q.deq();
                for(arc *p=N[now];p;p=p->next){
                    if(p->con > 0 && fa[p->j]==-1){
                        q.enq(p->j);
                        fa[p->j]=now;
                        from[p->j]=p;
                    }
                }
            }
            if(fa[999]==-1)break;
            //flow
            for(int now=999;now;now=fa[now]){
                if(flow>from[now]->con)
                    flow=from[now]->con;
            }
            if(!flow)break;
            for(int now=999;now;now=fa[now]){
                from[now]->con-=flow;
                from[now]->topair->con+=flow;
            }
            max+=flow;
        }
        puts(max==m?"YES":"NO");
    }
}