Page 2 of 2
Posted: Fri Nov 04, 2005 6:17 pm
by 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.
help 302
Posted: Mon Feb 12, 2007 7:16 pm
by 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);
}
Why 302 TLE?
Posted: Fri Oct 17, 2008 9:53 am
by 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.
Re: Why 302 TLE?
Posted: Fri Oct 17, 2008 10:01 am
by 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;
}
Re: 302 (John's trip) test cases
Posted: Tue Nov 23, 2010 10:32 pm
by 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;
}
Re: 302 - John's trip
Posted: Mon Feb 23, 2015 11:14 am
by 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.