10987 - Antifloyd

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

Moderator: Board moderators

Post Reply
rushel
Learning poster
Posts: 67
Joined: Sat Jan 22, 2005 5:57 am

10987 - Antifloyd

Post by rushel » Sat Feb 04, 2006 2:29 pm

Can this problem be solved using MST?

User avatar
Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:

Post by Abednego » Sun Feb 05, 2006 7:44 am

I don't think so, but if you find a solution, I would love to hear about it.
If only I had as much free time as I did in college...

rushel
Learning poster
Posts: 67
Joined: Sat Jan 22, 2005 5:57 am

Post by rushel » Sun Feb 05, 2006 7:52 am

Sorry for bothering u guys. I misunderstood the problem. Pardon me.

rushel
Learning poster
Posts: 67
Joined: Sat Jan 22, 2005 5:57 am

Post by rushel » Mon Feb 06, 2006 5:42 pm

I tried many time but i failed to attack the problem. Its driving me crazy. Can anybody give some hint.

User avatar
Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:

Post by Abednego » Mon Feb 06, 2006 5:47 pm

There is a hint in the problem's name.
If only I had as much free time as I did in college...

rushel
Learning poster
Posts: 67
Joined: Sat Jan 22, 2005 5:57 am

Post by rushel » Mon Feb 06, 2006 5:53 pm

Did i have to run floyd warshall while maximizing path lenght between (u,v)

User avatar
Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:

Post by Abednego » Mon Feb 06, 2006 5:57 pm

My next hint is this.

The Floyd-Warshall 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...

rushel
Learning poster
Posts: 67
Joined: Sat Jan 22, 2005 5:57 am

Post by rushel » Mon Feb 06, 2006 6:03 pm

So, I will try to remove the edges descending order from the matrix and check whether shortes paths holds

User avatar
Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:

Post by Abednego » Mon Feb 06, 2006 6:12 pm

My last hint is:

Figure out all the cases when the answer is "impossible". Then you should have a good idea how to solve the "possible" cases.
If only I had as much free time as I did in college...

rushel
Learning poster
Posts: 67
Joined: Sat Jan 22, 2005 5:57 am

Post by rushel » Tue Feb 07, 2006 5:51 am

I am getting WA:
Algo: Invalid Case: C[k]+C[k][v] <C[v] where k != u && k!= v

if not invalid
if(C[k]+C[k][v]==C[v]) then cancel edge(u,v);
where k!=u and k!=v

Can anyone give me some test cases?

rushel
Learning poster
Posts: 67
Joined: Sat Jan 22, 2005 5:57 am

Post by rushel » Tue Feb 07, 2006 12:19 pm

Thanks Abednego I got AC. I did mistake in reading input. Thanks Once Again For ur Help.

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko » Mon Jul 10, 2006 2:56 am

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.

User avatar
kbr_iut
Experienced poster
Posts: 103
Joined: Tue Mar 25, 2008 11:00 pm
Location: IUT-OIC, DHAKA, BANGLADESH
Contact:

Re: 10987 - AntiFloyd

Post by kbr_iut » Wed Sep 10, 2008 12:23 am

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 n-1 )
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==i||k==j||i==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<<n-1<<endl;
		for(i=1;i<n;i++)cout<<i<<" "<<i+1<<" "<<m[i][i+1]<<endl;	
		cout<<endl;
	}
	return 0;
}


if possible pliz anyone give me some more test cases.
thanx in advance.
It is tough to become a good programmer.
It is more tough to become a good person.
I am trying both...............................

calicratis19
Learning poster
Posts: 76
Joined: Mon Jul 21, 2008 8:50 am
Location: SUST,SYLHET,BANGLADESH.
Contact:

10987 - AntiFloyd

Post by calicratis19 » Tue Mar 09, 2010 8:08 am

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 :)

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!=node-1)
            {
                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

Post Reply

Return to “Volume 109 (10900-10999)”