Cod sursa(job #670116)

Utilizator Catah15Catalin Haidau Catah15 Data 28 ianuarie 2012 13:53:58
Problema Taramul Nicaieri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.72 kb
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>

using namespace std;

#define maxN 105

int ST[maxN][maxN], DR[maxN][maxN];
bool A[maxN][maxN], N;
int in[maxN], out[maxN];
int viz[maxN];


bool cuplaj (int x, int poz)
{
	if (viz[x] > N) return false;
	viz[x] ++;
	
	for (int i = 1; i <= N; ++ i)
	{
		if (i == x) continue;
		if (A[x][i]) continue;
		
		if (DR[i][0] < out[i])
		{
			DR[i][0] ++;
			DR[i][DR[i][0]] = x;
			
			if (ST[x][0] < poz)
			{
				ST[x][0] ++;
				ST[x][ST[x][0]] = i;
			}
			else ST[x][poz] = i;
			
			A[x][i] = true;
			
			return true;
		}
		else 
			for (int j = 1; j <= DR[i][0]; ++ j)
			{
				int q = 0;
				
				for (int t = 1; t <= ST[DR[i][j]][0]; ++ t) 
					if (ST[DR[i][j]][t] == i)
					{
						q = t;
						break;
					}
				
				if (cuplaj (DR[i][j], q))
				{
					A[DR[i][j]][i] = false;
					
					DR[i][j] = x;
					
					if (ST[x][0] < poz)
					{
						ST[x][0] ++;
						ST[x][ST[x][0]] = i;
					}
					else ST[x][poz] = i;
					
					A[x][i] = true;
					
					return true;
				}
			}
	}
	
	return false;
}

int main()
{
	freopen ("harta.in", "r", stdin);
	freopen ("harta.out", "w", stdout);
	
	scanf ("%d", &N);
	
	int S = 0;
	
	for (int i = 1; i <= N; ++ i)
	{
		scanf ("%d %d", &in[i], &out[i]);
		
		S += in[i];
	}
	
	bool ok = true;
	
	while (ok)
	{
		ok = false;
		
		memset (viz, 0, sizeof (viz));
		
		for (int i = 1; i <= N; ++ i)
			if (ST[i][0] < in[i] && cuplaj (i, ST[i][0] + 1)) ok = true;
	}
	
	printf ("%d\n", S);
	
	for (int i = 1; i <= N; ++ i)
		for (int j = 1; j <= ST[i][0]; ++ j) printf ("%d %d\n", i, ST[i][j]);
	
	return 0;
}