OJ Board

Code: Select all

ACC...  Thank you, Rio!
Can't believe I missed that ...
None of my test cases tested it ...  

Code: Select all

computer[n] = 0;

Code: Select all

return Solve(n+1);

Code: Select all

#include<cstdio>
#include<iostream>
#include<cstring>

using namespace std;


int a[300][300];
int task[300];
bool alpha[300];
char alloc[500];
bool seen[500];

bool bpm(int i)
{
	int j;
	for(j=0;j<10;j++)
		if(a[i][j] && alloc[j]=='_')
		{
			alloc[j]=i+'A';
			return true;
		}
	
	seen[i]=true;
	for(j=0;j<10;j++)if(a[i][j] && (alloc[j]-'A')!=i && !seen[j])
	{
		if(bpm(alloc[j]-'A'))
		{
			alloc[j]=i+'A';
			return true;
		}
	}
	return false;
}


int main(void)
{
	//freopen("259in.txt","r",stdin);
	char s[1000];
	int i,j,q;
	while(gets(s))
	{

		memset(a,0,sizeof(a));
		memset(alpha,false,sizeof(alpha));
		memset(alloc,'_',sizeof(alloc));
		
		if(strcmp(s,"")==0)
		{
			for(i=0;i<10;i++)
			{
				printf("%c",alloc[i]);
			}
			printf("\n");
			continue;
		}
		int p=s[0]-'A';
		task[p]=s[1]-'0';
		alpha[p]=true;
		for(i=3;s[i]!=';';i++)
		{
			q = s[i]-'0';
			a[p][q]=1;
		}

		while(1)
		{
			if(!gets(s))
				break;
			if(strcmp(s,"")==0)
				break;
			p=s[0]-'A';
			task[p]=s[1]-'0';
			alpha[p]=true;
			for(i=3;s[i]!=';';i++)
			{
				q=s[i]-'0';
				a[p][q]=1;
			}
		}

		int cnt=0;
		int flag=1;
		for(i=0;i<26;i++)if(alpha[i])
		{
			for(j=0;j<task[i];j++)
			{
				memset(seen,false,sizeof(seen));
				if(!bpm(i))
				{
					flag=0;
					break;
				}
			}
			if(!flag)
				break;
		}

		if(!flag)
		{
			printf("!\n");
		}
		else
		{
			for(i=0;i<10;i++)
			{
				printf("%c",alloc[i]);
			}
			printf("\n");
		}
	}
	return 0;
}

Code: Select all

A1 13579;
B1 02468;
C1 01;
D1 02;
E1 1;
F1 3;
P1 4;
Q1 5;
Z1 7;

Code: Select all

CEDFPQBZ_A

Code: Select all

Accepted!
I was forget the flow on v->u , fnet on COMPUTER -> APPLICATION
Thanks.

Code: Select all

#include <iostream>
#include <sstream>
using namespace std;

const int N = 38;
int C[N][N];
int F[N][N];

void clear()
{
	memset(C,0,sizeof(C));
	memset(F,0,sizeof(F));
}

const int s = 36;
const int t = 37;
const int inf = 1<<30;

int maxFlow()
{	
	int e[N], h[N];

	memset(e,0,sizeof(e));
	memset(h,0,sizeof(h));

	h[s] = N;

	for(int i = 0; i < N; ++i)
		if(i != s)
		{
			F[s][i] = C[s][i];
			F[i][s] = -F[s][i];
			e[i] = F[s][i];
		}
		
	for(int i = 0, j = 0, sz = 0, maxh[N]; ; )
	{
		if(!sz)
		{
			for(i=0; i < N; ++i)
				if(i != s && i != t && e[i])
				{
					if(!sz || h[i] > h[maxh[0]])
					{
						sz = 0;
						maxh[sz++] = i;
					}
					else if(h[i] == h[maxh[0]])
							maxh[sz++]=i;
				}								
		}

		if(!sz) break;

		while(sz > 0)
		{
			bool pushed = false;			
			i = maxh[sz-1];
			
			for(j=0; j < N; ++j)
				if(C[i][j] - F[i][j] > 0 && h[i]==h[j]+1)
				{
					pushed = true;
					int pf = min(C[i][j] - F[i][j], e[i]);
					F[i][j] += pf; F[j][i] = -F[i][j];
					e[i] -= pf; e[j] += pf;					
					if(e[i]==0) 
					{
						sz--;
						break;
					}
				}

			if(!pushed)
			{
				h[i] = inf;
				for(j=0; j < N; ++j)
					if(C[i][j]-F[i][j] > 0 && h[j]+1 < h[i])
						h[i] = h[j]+1;

				if(h[maxh[sz-1]] < h[i])
				{
					sz=0;
					break;
				}
			}				
		}
	}
	return e[t];
}

int main(int argv, char* arg[])
{
	#ifndef ONLINE_JUDGE
		freopen("in","r",stdin);		
	#endif	

	char buff[256];
	char comps[256];	
	int expected_flow = 0;

	clear();	
			
	while( 1 )
	{
		cin.getline( buff,256 );

		if(buff[0]=='\0')
		{
			bool cant = false;
			int flow = 0;
			
			if(expected_flow <= 10)
			{
				for(int i=0; i < 10; ++i)					
						C[26+i][t] = 1;

				flow = maxFlow();
			}
			else
				cant = true;

			if(expected_flow != flow || cant)
			{
				cout << '!' << endl;
			}
			else
			{
				for(int i = 26; i < s; ++i)
				{
					char c = '_';
					if(F[i][t] > 0)
					{
						for(int k = 0; k < 26; ++k)
						{
							if(F[k][i] > 0)
							{
								c = 'A' + k;
								break;
							}
						}
					}
					cout << c;
				}						
			}

			cout << endl;
			if(cin.eof()) return 0;						
			
			clear();
			expected_flow = 0;
			continue;
		}
		
		istringstream iss(buff);
		string ss;

		iss >> ss;

		if(ss[0] < 'A' || ss[0] > 'Z') continue;		

		int job =  ss[0] - 'A';				
		int sz=0;
		char ch = ' ';
		while(1)
		{
			iss >> ch;

			if(ch >= '0' && ch <= '9')
			{	
				comps[sz++] = ch-'0'+26;
			}
			else 
			{
				if(ch == ';')
				{
					for(int i=0;i<sz;++i) 						
							C[job][comps[i]] = 1;	
					
					C[s][job] += ss[1] - '0';
					expected_flow += ss[1] - '0';
				}
				
				break;
			}
		}		
	}			

	return 0;
}

Code: Select all

while (gets(buf)) {
    ...
    ...
    sscanf(buf, "%s%s", str1, str2);
    ...
    ...
    while (gets(buf)) {
        if (strlen(buf) <= 0)
            break;
        sscanf(buf, "%s%s", str1, str2);
        ...
        ...
    }
    ...
    ...
}