OJ Board

Code: Select all

2
6 6
L XL
XL XS
XS XXL
XXL M
S M
L XS
6 6
L XL
XL XS
XS XXL
XXL XL
S M
L XS

Code: Select all

YES
NO

Code: Select all

2
6 6
L XL
XL XS
XS XXL
XXL M
S M
L XS
6 6
L XL
XL XS
XS XXL
XXL XL
S M
L XS

Code: Select all

limit = 1

XXL: 2 3
XL: 0 1
L: 0 5
M: 3 4
S: 4
XS: 1 2 5

Code: Select all

<step1>
XXL: 2 3
XL: 0 1
L: 0 5
M: 3 
S: 
XS: 1 2 5

<step2>
XXL: 2 
XL: 0 1
L: 0 5
M: 
S: 
XS: 1 2 5

<step3>
XXL: 
XL: 0 1
L: 0 5
M: 
S: 
XS: 1 5

Code: Select all

             if(hole * limit < radish)
                System.out.println("NO");
              else
                System.out.println("YES");

Code: Select all

YES
NO

Code: Select all

#include<iostream>
#include<vector>
#include<string>

#define NN 1024 // the maximum number of vertices[0,n-1],[i][j] = i->j edge
#define MAX_CAP 2000000000000000000

using namespace std;

long int cap[NN][NN];// adjacency matrix (fill this up) [0, n-1]
long int fnet[NN][NN];// flow network  [0, n-1]
long int q[NN], qf, qb, prev[NN];// BFS
int size[6];
string si[6]={"XS","S","M","L","XL","XXL"};

long int fordFulkerson( long int n, long int s, long int t );
int s_to_i(string);

int main(){
	long int num,N,M;
	string temp;
	cin>>num;
	for(int knum=0;knum<num;knum++){
		cin>>N>>M;
		for(int kk=0;kk<6;kk++)
			size[kk]=0;
		for(int k1=0;k1<M+N+2;k1++)
			for(int k2=0;k2<M+N+2;k2++)
				cap[k1][k2]=0;
		for(int kM=0;kM<M;kM++){
			for(int k1=0;k1<2;k1++){
				cin>>temp;
				cap[N/6*s_to_i(temp)+size[s_to_i(temp)]][kM+N]=1;
				size[s_to_i(temp)]++;size[s_to_i(temp)]%=(N/6);

			}
		}
			for(int k1=0;k1<N;k1++)
		cap[N+M][k1]=1;
		for(int k1=0;k1<M;k1++)
			cap[k1+N][N+M+1]=1;


		/*for(int k1=0;k1<N+M+2;k1++)
			for(int k2=0;k2<N+M+2;k2++)
				if(cap[k1][k2]!=0)cout<<k1<<" "<<k2<<" "<<cap[k1][k2]<<endl;*/


		if(fordFulkerson(N+M+2,N+M,N+M+1)==M)
			cout<<"YES"<<endl;
		else cout<<"NO"<<endl;

	}
	return 0;
}

long int fordFulkerson( long int n, long int s, long int t ){
    memset( fnet, 0, sizeof( fnet ) );// init the flow network
    long int flow = 0;
    while( true ){
        memset( prev, -1, sizeof( prev ) );// find an augmenting path
        qf = qb = 0;
        prev[q[qb++] = s] = -2; //Enqueue
        while( qb > qf && prev[t] == -1 )//BFS //Dequeue
            for( long int u = q[qf++], v = 0; v < n; v++ )
                if( prev[v] == -1 && fnet[u][v] - fnet[v][u] < cap[u][v] )
                    prev[q[qb++] = v] = u;
        if( prev[t] == -1 ) break;// see if we're done
		long int bot = 0x7FFFFFFF;  
        for( long int v = t, u = prev[v]; u >= 0; v = u, u = prev[v] ) // get the bottleneck capacity
           bot = min(bot,cap[u][v]-fnet[u][v]+fnet[v][u]);
        for( long int v = t, u = prev[v]; u >= 0; v = u, u = prev[v] )// update the flow network
            fnet[u][v] += bot;
        flow += bot;
    }
    return flow;
}

int s_to_i(string s){
	for(int k=0;k<6;k++)
		if(s==si[k])return k;
}