Cod sursa(job #507651)

Utilizator cosmin79Carabet Cosmin Andrei cosmin79 Data 6 decembrie 2010 15:49:23
Problema Oras Scor 55
Compilator cpp Status done
Runda selectie-vianu-2011 Marime 1.89 kb
#include <stdio.h>
#include <queue>
#include <string.h>
#define NMAX 205
using namespace std;
int n,D[NMAX][NMAX];
char A[NMAX][NMAX],marc[NMAX][NMAX];
queue <int> Q;
char in[NMAX];
void bf(int x)
{
	Q.push(x); in[x]=1;
	int i,nod;
	while (!Q.empty())
	{
		nod=Q.front();
		Q.pop();
		in[nod]=0;
		for (i=1; i<=n; i++)
			if (nod!=i && A[nod][i]==1)
			{
				if (D[x][i]>D[x][nod]+1)
				{
					D[x][i]=D[x][nod]+1;
					if (!in[i])
						Q.push(i),in[i]=1;
				}
			}
	}
}
void calc_dist()
{
	int i,j;
	for (i=1; i<=n; i++)
	{
		for (j=1; j<=n; j++)
			D[i][j]=NMAX;
		D[i][i]=0;
		bf(i);
	}
}
inline int verif()
{
	int i,j;
	for (i=1; i<=n; i++)
		for (j=1; j<=n; j++)
			if (D[i][j]>2)
				return 0;
	return 1;
}
int main()
{
	freopen("oras.in","r",stdin);
	freopen("oras.out","w",stdout);
	scanf("%d",&n);
	int i,j,k,found;
	for (i=1; i<=n; i++)
	{
		for (j=i+1; j<=n; j++)
		{
			if (!marc[i][j])
			{
				marc[i][j]=1; marc[j][i]=1;
				A[i][j]=1;
				found=0;
				for (k=1; k<=n; k++)
					if (k!=i && k!=j)
					{
						if (marc[j][k]==1 && A[j][k]==0)
							continue ;
						if (marc[k][i]==1 && A[k][i]==0)
							continue ;
						marc[j][k]=1; marc[k][j]=1; 
						marc[k][i]=1; marc[i][k]=1;
						A[j][k]=1; A[k][j]=0; A[k][i]=1; A[i][k]=0;
						found=1;
						break ;
					}
				if (!found)
				{
					for (k=1; k<=n; k++)
						if (k!=i && k!=j)
						{
							if (marc[i][k]==1 && A[i][k]==0)
								continue ;
							if (marc[k][j]==1 && A[k][j]==0)
								continue ;
							marc[i][k]=1; marc[k][i]=1; 
							marc[k][j]=1; marc[j][k]=1;
							A[i][k]=1; A[k][i]=0; A[k][j]=1; A[j][k]=0;
							break ;
						}
				}
			}
		}
	}
	calc_dist();
	if (!verif())
	{
		printf("-1\n");
		return 0;
	}
	for (i=1; i<=n; i++)
	{
		for (j=1; j<=n; j++)
			printf("%d",A[i][j]);
		printf("\n");
	}
	return 0;
}