302 - John's trip

[hank]

I got Accepted after got WA many times.

If you are trying to solve it, you must realize:

There are something wrong in this problem.

The street number can be large than 44. ( I think it is less than 2000 )

And John lives at the street of the first line of each data block.
not the "number 1" street!

and you can just use DFS to solve it.
or you can use euler cycle method.

[Mr.south]

i use eulerian circuit to solve this question
but i got a problem
I have some problem when i got a vertex, this vertex has more than two edges, my code will choose the smallest num of vertex to put in the stack, but i think this is wrong

ex. when i got node 2, this node has edge 1, 2, 3, 4, 5. what edge should i choose and push the related vertex in the stack

this is part of my code

void find_circuit(int i)
{
int j, min;

if(degree == 0)
{
push(stack, i);
return;
}
for(j=0;j<45;j++) // check the whole neighbors
{
if(adj[j] > 0) //there exist more than 1 edges
{
if(visited[j] > 0) visited[j]--; //i use this to check whether the graph is connected
adj[j]--; //kill one edge (i, j) (j, i)
adj[j]--;
degree--;
degree[j]--;
find_circuit(j);
}
}
push(stack, i);
}

[porker2008]

I have solved 302 by using DFS Algorithm. However, I get TLE.

I don't know what kind of cases will lead to TLE. Can somebody tell me.

I find my program run fast on my computer even though the cases are very complicated.

I think I must ignore some special cases that beyond my thinking.

[porker2008]

Code: Select all

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

void check(int i,int loc);

vector<int> a1,a2,street;
int order[2000];
bool finish=false,pass=false;
int num;
bool used[2000];
bool checked[2000];

int main(){
    int b1,b2,st;
    while(cin>>b1>>b2){
                       a1.clear(); a2.clear(); street.clear();
                       if(b1==0&&b2==0) break;
                       a1.push_back(b1);
                       a2.push_back(b2);
                       cin>>st;
                       street.push_back(st);
                       while(cin>>b1>>b2){
                                          if(b1==0&&b2==0) break;
                                          a1.push_back(b1);
                                          a2.push_back(b2);
                                          cin>>st;
                                          street.push_back(st);
                       }
                       num=street.size();
                       memset(used,0,sizeof(used));
                       int loc=min(a1[0],a2[0]);
                       finish=false;
                       pass=false;
                       memset(order,0,sizeof(order));
                       check(0,loc);
                       if(pass){
                                for(int i=0;order[i]!=0;i++) {cout<<order[i]; if(order[i+1]!=0) cout<<" ";}
                                cout<<endl<<endl;
                       }
                       else
                       cout<<"Round trip does not exist."<<endl<<endl;
    }
    return 0;
}
//Using DFS to find the order.
void check(int i,int loc){
     if(i==street.size()&&loc==min(a1[0],a2[0])){pass=true;finish=true;return;}
     int min=-1;
     int tmin=2000;
     int num=0;
     for(int j=0;j<street.size();j++)
             if(!used[j]&&(a1[j]==loc||a2[j]==loc)) num++;
     for(int k=0;k<num&&!pass&&!finish;k++){
             int tmin=2000;
             int l=2000;
             for(int j=0;j<street.size();j++)
                     if(!used[j]&&(a1[j]==loc||a2[j]==loc)&&street[j]>min&&street[j]<tmin) {tmin=street[j];l=j;}
             min=street[l];
             used[l]=true;
             if(l==2000) {break;}
             if(a1[l]==loc) {order[i]=street[l]; check(i+1,a2[l]);}
             else {order[i]=street[l]; check(i+1,a1[l]);}
             used[l]=false;
             if(!pass) order[i]=0;
     }
     return;
}

[sami001]

i'm getting RTE... pls... somebody help me::

Code: Select all

#include <stdio.h>

int main()
{

	int j1,j2,r,i,k,a,b,c,H,m,n,p,p1,sum,j,q,l,s,t,u,junc[50][2],result[2000],search,flag,mem;

	while(1){

		int g[50][2000]={0},g1[50][2000]={0};
		a=0;
		b=0;
		n=0;
		flag=0;
		
		for(i=0;;i++)
		{
			
			scanf("%d %d",&j1,&j2);
			if(j1==0 && j2==0 && i==0){n=1;break;}
			else if(j1==0 && j2==0)break;
			scanf("%d",&r);
			
			if(i==0)
			{
				if(j1>j2)H=j2;
				else H=j1;
			}
			
			
			if(j1!=j2)
			{
				g[j1][r]=g1[j1][r]=1;
				g[j2][r]=g1[j2][r]=1;
			}
			
			else if(j1==j2)
			{
				g[j1][r]=g1[j1][r]=2;
				g[j2][r]=g1[j2][r]=2;
			}
			
			if(r>a)a=r;
			if(j1>b)
			{
				b=j1;
				if(j2>j1)b=j2;
			}
		}
		
		if(n==1)break;
		n=0;
		
		for(i=1;i<=b;i++)
		{
			sum=0;
			for(k=1;k<=a;k++)sum+=g[i][k];
			if(sum%2==1){printf("Round trip does not exist.\n");printf("\n");n=1;break;}
		}
	
	    if(n==1)continue;
	    i=H;
	    m=a+1;
	    junc[0][0]=H;
		
		
		p=0;
	    s=0;

	    while(p!=a)
		{

			search=0;
			if(flag==1)mem=result[p+1];
			
			n=0;
		    q=0;
		
		    for(j=1;j<=a;j++)if(g[i][j]==1)n++;
		

		    if(n<=1)
			{
			    for(j=1;j<=a;j++)if(g[i][j]==2)
				{
				    result[p+1]=j;
					g[i][j]=0;
				    p++;
				    q=1;
					search=1;
				}
				
			}

		    n=0;
			
			for(j=1;j<=a;j++){
				
				if(j==m)continue;
					
				if(g[i][j]==1)
				{
					
					if(q==0){
						 for(k=1;k<=a;k++){
							 if(g[i][k]==2 && k<j){g[i][k]=0;result[p+1]=k;search=1;p++;}
							 else if(g[i][k]==2 && k>j)break;
						 }
					}
					result[p+1]=j;
					p++;
					search=1;
					l=i;
					for(i=1;i<=b;i++)g[i][j]=0;
					
					break;
				  }
			}
			
			
			if(search==0){
				s--;
				i=junc[s][0];
			    m=1;
				if(flag==0)p1=p;
				
				flag=1;
				
				p=junc[s][1];
			    continue;
			}
			
			else if(search==1 && flag==1){


				for(t=p1;t>=p+1;t--){
					c=result[t];
					for(u=1;u<=b;u++)g[u][c]=g1[u][c];
				}
				for(u=1;u<=b;u++)g[u][mem]=g1[u][mem];
				
				flag=0;
			}
			
			m=j;
			for(k=1;k<=b;k++){
				if(g1[k][j]==1 && k!=l)i=k;
			}
		    
			s++;
		    junc[s][0]=i;
			junc[s][1]=p;
		}
		
		for(s=1;s<=a;s++)
		{
			if(s<a)printf("%d ",result[s]);
			else printf("%d\n\n",result[s]);
		}
			
		}
		
		return 0;

}

[dibery]

Note that the "lexicographical order" is not what we used for strings.
Rather, it's for numeric values.
For example, if "9 10" & "10 9" are both solutions, we should print "9 10" instead of "10 9" because 9 goes before 10.