SGU 125 – System of difference constraints

/* Nearly forget how to write bellman_ford...
 * System of difference constraints
 * for i-j <= t, add a edge(j,i)=t
 * add a src node and add edges (src, i)=0 for all node i
 * run bellman ford
 * a good pratice on dfs !!
 */
#include<cstdio>
#include<cstring>
#include<algorithm>
 
using namespace std;
 
 
const int dx[4]={-1,0,0,1};
const int dy[4]={0,-1,1,0};
 
int  C[5][5];
char S[5][5][6][5];
 
int B[4][4];
int n,N;
int G[10][10];
int U[100],V[100],W[100],E,D[10];
 
 
bool Bellman_Ford(int src)
{
	for(int i=0;i<=N;i++) D[i]=1<<29;
	D[src]=0;
 
	for(int i=0;i<N;i++)
		for(int j=0;j<E;j++)
			if(D[U[j]]+W[j]<D[V[j]])
				D[V[j]]=D[U[j]]+W[j];
 
	for(int j=0;j<E;j++)
		if(D[U[j]]+W[j]<D[V[j]])
			return false;
 
	int low=1<<29, high=-(1<<29);
	for(int i=0;i<N;i++)
	{
		low=min(low,D[i]);
		high=max(high,D[i]);
	}
 
	if(high-low>9) return false;
	else for(int i=0;i<N;i++) D[i]-=low;
 
	return true;
}
 
bool dfs(int now)
{
	int nx=now/n,ny=now%n;
	if(now==N) {			
		E=0;
		for(int i=0;i<N;i++)
		{
			for(int j=i+1;j<N;j++)
				if(G[i][j]==1) U[E]=j, V[E]=i, W[E]=-1, E++; //G[i][j]==1 i<j ==> i-j<=-1
				else if(G[i][j]==0) U[E]=i, V[E]=j, W[E]=-1, E++;	//G[i][j]==0 j<i ==> j-i<=-1
			U[E]=N, V[E]=i, W[E]=0, E++;
		}
 
		for(int i=0;i<n;i++)
			for(int j=0;j<n;j++)
				for(int k=0;k<4;k++)
				{
					int tx=i+dx[k], ty=j+dy[k], tn=tx*n+ty, sn=i*n+j;
					if(tx>=0 && tx<n && ty>=0 && ty<n && G[sn][tn]==-1) {
						U[E]=sn, V[E]=tn, W[E]=0, E++;
					}
				}
		if(Bellman_Ford(N)) return true;		
		return false;
	} else {		
		int a[4],b[4],an=0,t,tx,ty,tn;
		for(int k=0;k<4;k++)
		{
			tx=nx+dx[k]; ty=ny+dy[k]; tn=tx*n+ty;
			if(tx>=0 && tx<n && ty>=0 && ty<n && G[now][tn]==-1) a[an++]=tn;		
		}
 
		if(an<B[nx][ny]) return false;
		if(B[nx][ny]==0) return dfs(now+1);
		for(int k=0;k<C[an][B[nx][ny]];k++)
		{			
			for(int i=0;i<B[nx][ny];i++)
			{
				t=S[an][B[nx][ny]][k][i]-48;		
				G[a[t]][now]=0; G[now][a[t]]=1;
			}
			if(dfs(now+1)) return true;
			for(int i=0;i<B[nx][ny];i++)
			{
				t=S[an][B[nx][ny]][k][i]-48;
				G[a[t]][now]=G[now][a[t]]=-1;
			}
		}
		return false;
	}
}
 
void init()
{
	C[1][1]=1;	strcpy(S[1][1][0],"0");
	C[2][1]=2;	strcpy(S[2][1][0],"0"); strcpy(S[2][1][1],"1");
	C[2][2]=1;	strcpy(S[2][2][0],"01");
	C[3][1]=3;	strcpy(S[3][1][0],"0"); strcpy(S[3][1][1],"1"); strcpy(S[3][1][2],"2");
	C[3][2]=3;	strcpy(S[3][2][0],"01"); strcpy(S[3][2][1],"12"); strcpy(S[3][2][2],"02");
	C[3][3]=1;  strcpy(S[3][3][0],"012");
	C[4][1]=4;  strcpy(S[4][1][0],"0"); strcpy(S[4][1][1],"1"); strcpy(S[4][1][2],"2"); strcpy(S[4][1][3],"3");
	C[4][2]=6;  strcpy(S[4][2][0],"01"); strcpy(S[4][2][1],"02"); strcpy(S[4][2][2],"03"); strcpy(S[4][2][3],"12"); strcpy(S[4][2][4],"13"); strcpy(S[4][2][5],"23");
	C[4][3]=4;  strcpy(S[4][3][0],"012"); strcpy(S[4][3][1],"013"); strcpy(S[4][3][2],"023"); strcpy(S[4][3][3],"013");
	C[4][4]=1;  strcpy(S[4][4][0],"0123");
}
 
int main()
{	
	init();
	scanf("%d",&n); N=n*n;
 
	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++) scanf("%d",&B[i][j]);
 
	memset(G,-1,sizeof(G));
 
	if(dfs(0)) {
		for(int i=0;i<n;i++)
		{
			for(int j=0;j<n;j++)
				printf("%d ",D[i*n+j]);
			printf("\n");
		}
	} else {
		printf("NO SOLUTION\n");
	}
	return 0;
}

Leave a Reply

Your email address will not be published.