10462 - Is There A Second Way Left?

All about problems in Volume 104. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

ditrix
New poster
Posts: 33
Joined: Sat Mar 01, 2003 12:38 am
Location: Paris

10462 - Is There A Second Way Left?

I don't know where I have a mistake...

I use the next algorithm:

Code: Select all

0. Make a graph with the vertex - neighbors and the edges - direct conections.

1. Launch DFS and calculate the number of visited vertex. If this number is different from number total of vertex: print "No way", return
2.  If number of vertex is equal to number of edges + 1: print "No second way", return
3. Search the minimum covering tree and his price Pmin
4. For each edge  of the minimum covering tree do:
4.1 Delete this edge from the graph
4.2 Launch DFS and if the new graph isn't connexe go to 4.6
4.3  Search the minimum covering tree and his price P for this new graph
4.4  If P==Pmin go to 5
4.5 If P minimize the price of second-way-tree memorize it
4.6 Undelete the edge
5. Print P, return

Is it correct ?
@+!
DitriX

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
Do you consider this:
there may be multiple connections between two ends
For example the input:
1
3 4
1 2 1
2 3 1
1 3 3
1 3 4
Output is:
Case #1 : 4

My first program had the mistake that it printed 3 in this case.

ditrix
New poster
Posts: 33
Joined: Sat Mar 01, 2003 12:38 am
Location: Paris
Yes, this case is ok, and all that concern the multiple connections seems to be all right.
I tested my program with many possible cases (v=1 or e=0 included), but I havn't fixed an error.

Am I right to suppose that if v=1 and for all e the answer is "No second way"?
@+!
DitriX

shohag sust cse
New poster
Posts: 4
Joined: Tue Aug 06, 2002 11:38 am
For this problem i consider following thing's but got WA:Look plz:
1.when i take the input i consider the lowest cost edge.
Like:
if 1 2 10
1 2 5
1 2 11
in this case i consider 5 and all the other store in a struct and finaly all the
extra cost sort according to there cost.i.e,
2 3 10
3 2 5
3 4 5
then the cost matrix will contain
1 2 5
2 3 5
3 4 5
now after sorting the struct i replace 1 2 5 by 1 2 10 because of second
mst.For this input out put will for minimum 15 and the second 20.Is my logic clear.Plz help me.
All time i
nv1=stru[0].v1
nv2=stru[0].v2;
len=stru[0].len;

and replace as

cost[nv1][nv2]=cost[nv2][nv1]=len;

Now Prims.

mido
Learning poster
Posts: 78
Joined: Sun Jun 16, 2002 9:48 pm
Location: Cairo,Egypt

10462 - Is There A Second Way Left ?

Is it correct that the problem here is to find the 2nd minimum spanning tree? I'd also aprreciate any tricky input - output set to check my code:

Code: Select all

#include <iostream.h>

struct node{
int x;
int y;
int cost;
bool change;
} edge[210];

long long t,cur,i,j,k,v,e,x,y,cost,lim,count,sum;
bool found1,found2;
int parent[150];

int findpar(int x)
{
while (parent[x]!=-1)
x=parent[x];
return x;
}

void main()
{
cin>>t;
cur=0;
while (++cur<=t)
{
cin>>v>>e;
lim=0;
found1=false;
found2=false;
j=1;

for (i=1;i<=v+1;i++)
parent[i]=-1;

for (i=1;i<=e;i++)
{
cin>>x>>y>>cost;
j=1;
for (j=1;j<=lim && cost>=edge[j].cost;j++){}
for (k=lim+1;k>=j+1;k--) edge[k]=edge[k-1];
edge[j].x=x;
edge[j].y=y;
edge[j].cost=cost;
edge[j].change=false;
lim++;
}

cout<<"Case #"<<cur<<" : ";
if (e<v-1) {cout<<"No way"<<endl;continue;}
if (v==1) {cout<<"No second way"<<endl;continue;}

lim=e;
count=0;
sum=0;
i=1;

while (count<v-1 && i<=lim)
{
x=edge[i].x;
y=edge[i].y;

if (findpar(x)==findpar(y))
{i++;continue;}

count++;
edge[i].change=true;
parent[findpar(x)]=findpar(y);
sum+=edge[i].cost;
i++;
}

if (count==v-1) found1=true;
if (e==v-1 && found1) {cout<<"No second way"<<endl;continue;}

if (count==v-1)
{
int k=i-1;
bool done=false;

while (!done && k>0)
{
if (!edge[k].change)
{k--;continue;}

for (i=1;i<=v+1;i++)
parent[i]=-1;

sum=0;
count=0;
i=1;

while (count<v-1 && i<=lim)
{
x=edge[i].x;
y=edge[i].y;

if (i==k || findpar(x) == findpar(y))
{i++;continue;}

count++;
parent[findpar(x)]=findpar(y);
sum+=edge[i].cost;
i++;
}

if (count==v-1) {found2=true;done=true;}
else k--;
}
}
if (found2) cout<<sum<<endl;
else if (found1) cout<<"No second way"<<endl;
else cout<<"No way"<<endl;
}
}


miras
Learning poster
Posts: 98
Joined: Sat Jun 14, 2003 1:45 pm
HM..

I think that ithis code is quite ... strange to udestand..

Can u explain it how does o\it work ??

Bcs. i can help u
Remember Never Give Up
Regrads
Miras

miras
Learning poster
Posts: 98
Joined: Sat Jun 14, 2003 1:45 pm
HM..

I think that ithis code is quite ... strange to udestand..

Can u explain it how does o\it work ??

Bcs. i can help u
Remember Never Give Up
Regrads
Miras

lonelyone
Learning poster
Posts: 65
Joined: Sat Feb 19, 2005 6:53 pm
My algorithm:

Code: Select all

1. using vector to store multi-edge graph
2. compute MST for the first mst distance
a) if first distance doesn't exist, then output "No way", then exit
b) if n==0 && m==0, output "NO way", then exit
else continue
3. if n==m+1, output "No second way"
4. using first mst's parent path, scan the path again
try to remove one edge from graph
and do a second MST
a) if second distance doesn't exist, then output "No second way", exit
b) if second distance exist, then output the second distance
that's all

did I miss something, could someone give me so more test cases
please

lonely

mido
Learning poster
Posts: 78
Joined: Sun Jun 16, 2002 9:48 pm
Location: Cairo,Egypt
by "try to remove one edge from graph" I presume one of the edges in the first MST, am I right? In that case, that should work(as far as I can remember... )..

lonelyone
Learning poster
Posts: 65
Joined: Sat Feb 19, 2005 6:53 pm
No one want to help us out...

stubbscroll
Experienced poster
Posts: 151
Joined: Tue Nov 16, 2004 7:23 pm
Location: Norway
Contact:
Mido, your code fails this case:

Code: Select all

1
4 7
3 4 486
2 4 851
4 1 705
3 2 8
2 1 59
4 1 73
2 1 114
Your code outputs 553, the correct answer is 195.

Lonelyone, your algorithm looks correct. According to the problem description, there is no graph with 0 vertices in the input, so you need not check that (although I haven't tested this with assert yet). I can't confirm the correctness though, as I don't have AC yet.

lonelyone
Learning poster
Posts: 65
Joined: Sat Feb 19, 2005 6:53 pm
Thanks for your reply.
I got the same result as you of your test case.
So, maybe I will examine my code for a while.

anouk
New poster
Posts: 1
Joined: Mon Mar 05, 2007 9:55 pm
Could someone please post some tests? I followed the instructions on algorithmist.com, and for the test posted here my output is correct. I just can't see where I've made my mistake.

nymo
Experienced poster
Posts: 149
Joined: Sun Jun 01, 2003 8:58 am
Location: :)

Test Cases please...

I get correct answers for the inputs I 've found... Some more test cases needed. What is the catch? I am getting WAs
I 've entirely used 32-bit ints. Is it okay? No range for cost value is specified ...
regards,
nymo

pradeepr
New poster
Posts: 21
Joined: Fri May 25, 2007 11:52 am
Location: India

Re: 10462 - Is There A Second Way Left ?

I am getting WA

I tried to solve this problem by first finding a MST using kruskals and then finding the max[u,v] for all vertices u ,v in the MST and using this further to find the second MST.

MY code gives right outputs for all the test cases given above in this topic..
Can some check my code and please let me know of what is wrong with my code

Code: Select all

#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<cstdio>
#include<map>
#include<vector>
using namespace std;
typedef struct node
{
struct node* head; //head of the disjoint set
struct node* next; // next node of the disjoint set
int label;
}node;

typedef struct edge
{
int inlabel; //invertex label
int outlabel;//outvertex label
int weight;   //weight of the edge
bool belongs; //indicates whether it belongs to MST or not
}edge;

void make_set(node &N) // makes a single node disjoint set
{
N.head=&N;
N.next=NULL;
}

node * find_set(node N) // returns the head of the list in which the node N is placed
{

return N.head;
}

void find_union(node *a, node *b,map<node*,node*> &M) //union of 2 disjoint sets given their heads
{
node *tail1=M[a];
tail1->next=b;
M.erase(b);
while(b->next !=NULL)
{
b->head=a;
b=b->next;
}
b->head=a;
M[a]=b;
}

int compare(const void *a,const void *b) // compare function to sort the edges based on their weights
{
edge x=*(edge*)a;
edge y=*(edge*)b;
if(x.weight >  y.weight)
return 1;
else
return -1;
}

void DFS_FILL_MAX_VISIT(int u,int x,int size,int **G,vector<int>& max) // find an edge of max weight on the unique path  from u to every vertex v and stores it in max[v]
{
for(int v=0;v<size;v++)
{
if( G[x][v]>0 && max[v]==0 && v!=u)
{

if(x==u ||( G[x][v] >max[x]))
max[v]=G[x][v];
else
max[v]=max[x];

DFS_FILL_MAX_VISIT(u,v,size,G,max);
}
}
}

int main()
{
int num_cases,N,num_edges;
int temp1,temp2;
int temp3;
cin >>num_cases;
for(int k=0;k<num_cases;k++)
{
cin>>N;
unsigned long w=0,w2=1000000;
node *vertices=new node[N];
cin>>num_edges;
edge *edges=new edge[num_edges];

map<node*,node*> M;
node *head1,*head2;

int ** G= new int*[N]; //MST to be built
for(int i=0;i<N;i++)
{
G[i]=new int[N];
for(int j=0;j<N;j++)	//initialization.. an edge G[i][j]=0 implies there is no edge between vertices i and j
G[i][j]=0;
}
//using kruskals algorithm to build a MST
for(int j=0;j<N;j++)
{
(vertices[j]).label=j;
M[vertices+j]=vertices+j;  //linked list representation in which the map M is used to find the tail of list given the head  i.e M[head]=tail
make_set(vertices[j]);

}

temp3=0;
for(int j=0;j<num_edges;j++)
{
cin>>temp1>>temp2>>temp3;
edges[j].inlabel=temp1-1;
edges[j].outlabel=temp2-1;
edges[j].weight=temp3;
edges[j].belongs=false;

}
qsort(edges,num_edges,sizeof(edge),compare);

for(int j=0;j<num_edges;j++)
{
head1=find_set(vertices[edges[j].inlabel]);
head2=find_set(vertices[edges[j].outlabel]);
if(head1!=head2)
{
find_union(head1,head2,M);
w+=edges[j].weight;
edges[j].belongs=true;
G[edges[j].outlabel][edges[j].inlabel]=G[edges[j].inlabel][edges[j].outlabel]=edges[j].weight;
}
}
cout<<"Case #"<<k+1<<" : ";
if(M.size()>1)
cout<<"No way";
else
{

w2=1000000;
for(int j=0;j<num_edges;j++)
{
int u,v;
if(!edges[j].belongs)
{
vector<int> temp(N,0);
u=edges[j].inlabel;
v=edges[j].outlabel;
DFS_FILL_MAX_VISIT(u,u,N,G,temp);
if( (edges[j].weight-temp[v])< w2)
{
w2=(edges[j].weight-temp[v]);
}
}
}
if(w2==1000000)
cout<<"No second way";
else
cout<<w+w2;
}
cout<<'\n';
}
return(0);
}