10987  Antifloyd
Moderator: Board moderators
10987  Antifloyd
Can this problem be solved using MST?

 A great helper
 Posts: 281
 Joined: Tue Sep 10, 2002 5:14 am
 Location: Mountain View, CA, USA
 Contact:
My next hint is this.
The FloydWarshall algorithm takes an adjacency matrix and returns a shortest path matrix. In this problem, you get an shortest path matrix and have to produce the original adjacency matrix. Since there are multiple possible answers, I am asking you for the matrix with as many 0 entries as possible (as few edges as posssible).
The FloydWarshall algorithm takes an adjacency matrix and returns a shortest path matrix. In this problem, you get an shortest path matrix and have to produce the original adjacency matrix. Since there are multiple possible answers, I am asking you for the matrix with as many 0 entries as possible (as few edges as posssible).
If only I had as much free time as I did in college...
I don't know much about graphs so I thought about MST first, too (go me). As in  find MST of the shortest path matrix then do the Floyd's on it and compare it with the original one. If they are the same, print the tree. That doesn't work (well, works for the sample input, heh). I have no idea why it should or shouldn't work, though
Anyway  I just wanted to mention that input contains blank lines.
Anyway  I just wanted to mention that input contains blank lines.

 Experienced poster
 Posts: 103
 Joined: Tue Mar 25, 2008 11:00 pm
 Location: IUTOIC, DHAKA, BANGLADESH
 Contact:
Re: 10987  AntiFloyd
I am getting WA. I tried with many inputs but failed to get the bugs.Can anyone help?
i just consider invalid where m[k]+m[k][j]<m[j]
and if not invalid then i just print the value of i i+1 value (where i is from 1 to n1 )
is my algo correct?
here is my code.
if possible pliz anyone give me some more test cases.
thanx in advance.
i just consider invalid where m[k]+m[k][j]<m[j]
and if not invalid then i just print the value of i i+1 value (where i is from 1 to n1 )
is my algo correct?
here is my code.
Code: Select all
#include<iostream>
#include<algorithm>
using namespace std;
long n,e,m[200][200],sum;
bool antifloyed(){
int i,j,k;
for(k=1;k<=n;k++){
for(i=1;i<=n;i++){
for(j=1;j<=n;j++){
if(k==ik==ji==j)continue;
if(m[i][k]+m[k][j]<m[i][j])return true;
}
}
}
return false;
}
int main(){
long t,x=0,i,j;
//freopen("1.txt","r",stdin);
cin>>t;
while(t){
cout<<"Case #"<<++x<<":\n";
cin>>n;
fill(m[0],m[n+1],0);
for(i=2;i<=n;i++){
for(j=1;j<i;j++){
cin>>m[i][j];
m[j][i]=m[i][j];
}
}
if(antifloyed()){cout<<"Need better measurements.\n\n";continue;}
cout<<n1<<endl;
for(i=1;i<n;i++)cout<<i<<" "<<i+1<<" "<<m[i][i+1]<<endl;
cout<<endl;
}
return 0;
}
thanx in advance.
It is tough to become a good programmer.
It is more tough to become a good person.
I am trying both...............................
It is more tough to become a good person.
I am trying both...............................

 Learning poster
 Posts: 76
 Joined: Mon Jul 21, 2008 8:50 am
 Location: SUST,SYLHET,BANGLADESH.
 Contact:
10987  AntiFloyd
I tried it with floyd and mst together. But got wa.
my approach:
1) First run a floyd with the given floyd matrix and see if there is a better path.If there is a shorter path then its impossilbe. else i run a kruskel with the given floyd matrix . And then i print the edges. I am not sure if its the correct approach.Can anyone please clarify this for me. Thanks in advance
my approach:
1) First run a floyd with the given floyd matrix and see if there is a better path.If there is a shorter path then its impossilbe. else i run a kruskel with the given floyd matrix . And then i print the edges. I am not sure if its the correct approach.Can anyone please clarify this for me. Thanks in advance
Code: Select all
#include<stdio.h>
#include<stdlib.h>
int node,rank[1001],parent[1001],i,j,k,u,v,pos[1002][3],edge,test,mat[102][102],kase;
bool flg;
typedef struct{
int x,y,z;
}Ind;
Ind ar[10011],ans[10011];
int cmp(const void *a,const void *b)
{
Ind *X = (Ind *) a;
Ind *Y = (Ind *) b;
if(X>y == Y>y)return X>z  Y>z;
return X>y  Y>y;
}
int cmp1(const void *a,const void *b)
{
Ind *X = (Ind *) a;
Ind *Y = (Ind *) b;
return X>x  Y>x;
}
int Find_Set(int x)
{
if(x != parent[x] )
parent[x]=Find_Set(parent[x]);
return parent[x];
}
void Link(int x,int y)
{
if(rank[x]>rank[y])
parent[y]=x;
else
{
parent[x]=y;
if(rank[x]==rank[y])
rank[y]=rank[y]+1;
}
}
int main()
{
scanf("%d",&test);
while(test)
{
scanf("%d",&node);
k=0;
for(i=0;i<node;i++) parent[i] = i,rank[i] = 0;
for(i=1;i<node;i++)
{
for(j=0;j<i;j++)
{
scanf("%d",&u);
ar[k].x = u ;
ar[k].y = j ;
ar[k++].z = i ;
mat[j][i] = mat[i][j] = u;
}
mat[i][i]=0;
}
edge = k;
flg = 0;
for(k=0;k<node && !flg;k++)
for(i=0;i<node && !flg;i++)
for(j=0;j<node;j++)
if(mat[i][j] > mat[i][k]+mat[k][j])
{
flg = 1;
break;
}
printf("Case #%d:\n",++kase);
if(!flg)
{
qsort(ar,edge,sizeof(Ind),cmp1);
/* for(i=0;i<edge;i++)
printf("%d %d %d\n",ar[i].x,ar[i].y+1,ar[i].z+1);*/
k=0;
for( i=0 ; i<edge ; i++ )
{
u=Find_Set(ar[i].y);
v=Find_Set(ar[i].z);
if(u!=v)
{
Link(u,v);
ans[k].x = ar[i].y;
ans[k].y = ar[i].z;
ans[k++].z = ar[i].x;
}
}
qsort(ans,k,sizeof(Ind),cmp);
if(k!=node1)
{
flg = 1;break;
}
for(i=0;i<k;i++)
printf("%d %d %d\n",ans[i].x+1,ans[i].y+1,ans[i].z);
}
if(flg) printf("Need better measurements.\n");
printf("\n");
}
return 0;
}
Heal The World