OJ Board

Posted: **Sat Nov 19, 2005 11:31 am**

ayon wrote:did i write bf? i think it's bfs(breadth first search), not bf(boyfriend).

I am new to C++ so i don't know bfs as well, can you kindly tell me what it is? thanks.

Posted: **Sat Nov 19, 2005 7:22 pm**

bfs is a graph algorithm. You better see your algorithm book for bfs. it is too large to describe in the forum. You cannot understand without proper figure. the procedure and description takes at least 4-5 pages with enough figures. once you learn bfs, many problems(graphs) will be very easy to solve very quickly.

best regards

Posted: **Sat Nov 19, 2005 7:46 pm**

Yap, bfs does the trick, but i am confused .... whats the prob with my code? I got WA

here is my c code :

#include<stdio.h>

unsigned long P[1010];
unsigned long a[1005][1005];

void setP(unsigned long n)
{
unsigned long i;
P[0]=0;
for(i=1;i<n;i++)
{
P=2000;
}
return;
}

void refresh(unsigned long p)
{
unsigned long i,j;

for(i=0;i<p;i++)
{
for(j=0;j<p;j++)
{
a[j]=0;
}
}
return;
}

void sort(unsigned long p)
{
unsigned long i,j,temp;
for(i=0;i<p;i++)
{
for(j=i+1;j<p;j++)
{
if(P>P[j])
{
temp=P;
P=P[j];
P[j]=temp;
}
}
}
return;
}

void calculate(unsigned long p)
{
unsigned long i,j;
for(i=0;i<p;i++)
{
for(j=0;j<p;j++)
{
if(a[j] && (P+1)<P[j])
{
P[j]=P+1;
}
}
sort(p);
}

return;
}

unsigned long main(void)
{
unsigned long test,tc;
unsigned long p,d;
unsigned long i;
unsigned long r,c;
scanf("%lu",&test);
for(tc=0;tc<test;tc++)
{
scanf("%lu%d",&p,&d);
refresh(p);
setP(p);
for(i=0;i<d;i++)
{
scanf("%lu%d",&r,&c);
a[r][c]=1;
a[c][r]=1;
}
calculate(p);
for(i=1;i<p;i++)
{
printf("%lu\n",P);
}
printf("\n");
}
return 0;
}

Posted: **Sat Nov 19, 2005 7:50 pm**

Soarer wrote:
ayon wrote:did i write bf? i think it's bfs(breadth first search), not bf(boyfriend).
I am new to C++ so i don't know bfs as well, can you kindly tell me what it is? thanks.

Well , u may use internet to know abou bfs, its not a tough one....the book of Cormen is also cool

Posted: **Sat Nov 19, 2005 8:09 pm**

misof wrote:
Wei-Ming Chen wrote:Oh~ That line is check code. I will delete when I submit it.
And why the outputs are 1 & 2
I thought it was 1 & (can't wrote it)
The order of the dances doesn't matter. Even if 2 danced with 1 before 1 danced with Don Guilianni, the D. G. number of 2 is still 2.

hey my code does print right those two outputs , still WA

Code: Select all

#include<stdio.h>


unsigned long P[1010];
unsigned long a[1005][1005];

void setP(unsigned long n)
{
	unsigned long i;
	P[0]=0;
	for(i=1;i<n;i++)
	{
		P[i]=2000;
	}
	return;
}

void refresh(unsigned long p)
{
	unsigned long i,j;

	for(i=0;i<p;i++)
	{
		for(j=0;j<p;j++)
		{
			a[i][j]=0;
		}
	}
	return;
}

void sort(unsigned long p)
{
	unsigned long i,j,temp;
	for(i=0;i<p;i++)
	{
		for(j=i+1;j<p;j++)
		{
			if(P[i]>P[j])
			{
				temp=P[i];
				P[i]=P[j];
				P[j]=temp;
			}
		}
	}
	return;
}

void calculate(unsigned long p)
{
	unsigned long i,j;
	for(i=0;i<p;i++)
	{
		for(j=0;j<p;j++)
		{
			if(a[i][j] && (P[i]+1)<P[j])
			{
				P[j]=P[i]+1;
			}
		}
		sort(p);
	}
	
	return;
}

unsigned long main(void)
{
	unsigned long test,tc;
	unsigned long p,d;
	unsigned long i;
	unsigned long r,c;
	scanf("%lu",&test);
	for(tc=0;tc<test;tc++)
	{
		scanf("%lu%d",&p,&d);
		refresh(p);
		setP(p);
		for(i=0;i<d;i++)
		{
			scanf("%lu%d",&r,&c);
			a[r][c]=1;
			a[c][r]=1;
		}
		calculate(p);
		for(i=1;i<p;i++)
		{
			printf("%lu\n",P[i]);
		}
		printf("\n");
	}
	return 0;
}

Posted: **Sat Nov 19, 2005 8:13 pm**

implemention often makes trouble when that can be solved with known algo. try the following input

Code: Select all

your program gives

Code: Select all

1
1
2

but it should be

Code: Select all

2
1
1

better try with bfs, that will make your life easier...

Posted: **Wed Dec 07, 2005 4:47 pm**

here is my code

Code: Select all


code removed after AC....... :)

i use bfs.But i donno where is my wrong.Give me sm i/o.

Posted: **Wed Dec 07, 2005 6:23 pm**

I totally overlooked the line D<=p(p-1)/2.But i think they should give me RE in stead of WA.

Posted: **Sat Apr 01, 2006 6:34 am**

I too used BFS.
It's still giving WA.

Can u tell me what u did to solve ur problem?[/code]

Posted: **Sat Apr 01, 2006 6:40 am**

I too used BFS.
but it is giving WA.
Can smbd help me?
Here is the code-

Code: Select all

#include<stdio.h>
int main(){
        int dance[1000][1000],i,j,p,d,t,k,a,b,don[1000],c[1000];
        scanf("%d",&t);
        don[0]=0;
        for(i=0;i<t;i++){
                scanf("%d%d",&d,&p);
                for(j=0;j<d;j++)
                        for(k=0;k<d;k++)
                                dance[j][k]=-1;
                for(j=0;j<d;j++)
                        don[j]=c[j]=-1;
                for(j=0;j<p;j++){
                        scanf("%d%d",&a,&b);
                        dance[a][b]=dance[b][a]=1;
                }
                j=0,p=1;
                don[0]=0;
                c[0]=0;
                while(j!=d){
                        for(k=0;k<d;k++){
                                if(dance[j][k]==1 && c[k]==-1){
                                        don[p]=k;
                                        p++;
                                        c[k]=c[j]+1;
                                }
                        }
                        j++;
                }
                for(j=1;j<d;j++)
                        printf("%d\n",c[j]);
                printf("\n");
        }
        return 0;
}

Posted: **Sat Apr 01, 2006 9:35 am**

For this question, i used BFS.
But it's giving WA.
Can smbd help me?
Here is the code :

Code: Select all

#include<stdio.h>
int main(){
        int dance[1000][1000],i,j,p,d,t,k,a,b,don[1000],c[1000];
        scanf("%d",&t);
        don[0]=0;
        for(i=0;i<t;i++){
                scanf("%d%d",&d,&p);
                for(j=0;j<d;j++)
                        for(k=0;k<d;k++)
                                dance[j][k]=-1;
                for(j=0;j<d;j++)
                        don[j]=c[j]=-1;
                for(j=0;j<p;j++){
                        scanf("%d%d",&a,&b);
                        dance[a][b]=dance[b][a]=1;
                }
                j=0,p=1;
                don[0]=0;
                c[0]=0;
                while(j!=d){
                        for(k=0;k<d;k++){
                                if(dance[j][k]==1 && c[k]==-1){
                                        don[p]=k;
                                        p++;
                                        c[k]=c[j]+1;
                                }
                        }
                        j++;
                }
                for(j=1;j<d;j++)
                        printf("%d\n",c[j]);
                printf("\n");
        }
        return 0;
}

Posted: **Sun May 07, 2006 6:19 pm**

sorry for late reply.

my bfs approach......
psudocode

Code: Select all

	for(k=0 to inf){
		for(i=0 to num_of_guests_of_(k-1)th_step){
			for(j=0 to D(num_of_dancing_couple) ){
				if(guest_1 of j_th couple alredy marked){
					check if guest_2 alredy marked or not;
				}
				else if(guest_2 of j_th couple alredy marked){
					check if guest_1 alredy marked or not;
				}
			}
		}
	}

here is the bfs-code part....

Code: Select all



        st[0][0]=0;
        t[0]=1;

        for(k=0;;k++){
            t[(k+1)%2]=0;
            for(i=0;i<t[k%2];i++){           
                for(j=0;j<d;j++){
                    if(d1[j]==st[k%2][i]){
                        if(mark[d2[j]]>=mark[d1[j]]+1){
                            mark[d2[j]]=mark[d1[j]]+1;
                            st[(k+1)%2][t[(k+1)%2]++]=d2[j];
                        }    
                    } 
                    else if(d2[j]==st[k%2][i]){
                        if(mark[d1[j]]>=mark[d2[j]]+1){
                            mark[d1[j]]=mark[d2[j]]+1;
                            st[(k+1)%2][t[(k+1)%2]++]=d1[j];
                        }  
                    }      
                }    
            } 
            if(t[(k+1)%2]==0)break;              
        }

Posted: **Sat Aug 12, 2006 9:54 pm**

Ankur Jaiswal wrote:For this question, i used BFS.
But it's giving WA.
Can smbd help me?
Here is the code :

Your code isn't working for

Code: Select all

The correct output:

Code: Select all

Posted: **Tue Jul 17, 2007 12:05 am**

Hello, I cant find the error of this code, but I get WA.

Code: Select all

AC

Thank you.

Posted: **Tue Jul 17, 2007 4:38 pm**

Can anyone help me to find the wrong? My code is right for all inputs for this problem...

OJ Board

10959 - The Party, Part I

10959 - The Party, Part I

Problem in 10959

Problem in 10959

10959 - The Party, Part I

Re: 10959 The Party Part I.... Getting WA :(