1 / 3
Apr 2012

spoj.pl/problems/BLINNET/

Tried with all my inputs and is working good .. not able to figure out mistake ..

My approach
node ->i -- Start vertex
node ->j -- End vertex
node ->c -- Cost

Scanning all the edges into a array of Nodes .. Sorting them with Radix sort (Bit wise from LSB for 32 bits)

Optimization - I am not storing edges which are already stored.
I mean
scanf("%d %lld",&j,&co);
if(j>i) -- This statement skips edges connecting from current node to already inputted nodes (j - destination , i - present )

Then using Kruskal's algorithm .. Keeping track of visited nodes with a boolean array and running the loop till i visit n nodes.

#include <cstdio>
class node
{
public:
	int i,j;
	unsigned int c;
	node()
    { }
	node (int a,int b,long long d)
	{
		i=a;
		j=b; c=d;
	}
};
node arr[1000000],arr2[1000000],arr3[1000000];
int ctr;
bool visited[10020];
void radsort(int len)
{
	int m,f1,f2,p=0;
	for(long long i=1;p<=32;i=i<<1,p++)
	{
		f1=0; f2=0;
		for(int j=0;j<len;j++)
			if(((arr[j].c) & i) == 0 )
				arr2[f1++]=arr[j];
			else
				arr3[f2++]=arr[j];
		m=0;
		for(int j=0;j<f1;j++)
			arr[m++]=arr2[j];
		for(int j=0;j<f2;j++)
			arr[m++]=arr3[j];
	}
}
long long kruks(int n)
{
	int i,j,k=-1,cn=0,ii,jj;
	long long ans=0;
	for(i=0;i<=n;i++)
		visited[i]=0;
	while(cn<n)
	{
		k++;
		ii=arr[k].i; jj=arr[k].j;
		if(visited[ii]==1 && visited[jj]==1)
			continue;
		if(visited[ii]==0 && visited[jj]==0)
			cn++;
		visited[ii]=visited[jj]=1;
		ans+=arr[k].c;
		cn++;
	}
    return ans;
}
int main()
{
	int t,n,p,mr,i,j,k;
	long long co;
	scanf("%d",&t);
	while(t--)
	{
		ctr=0;
		scanf("%d",&n);
		for(i=1;i<=n;i++)
		{
			scanf("%*s%d",&p);
			while(p--)
			{
				scanf("%d %lld",&j,&co);
				if(j>i)
				{
					node n(i,j,co);
					arr[ctr]=n;
					ctr++;
				}
			}
		}
		radsort(ctr);
		printf("%lld\n",kruks(n));
	}
	return 0;
}

Thanks smile

  • created

    Apr '12
  • last reply

    Apr '12
  • 2

    replies

  • 191

    views

  • 2

    users

  • 1

    link

Solved it using Prime's .. But still I wanted to know whats wrong with this algorithm

And also .. This is the 1st time I implemented Radix sort . So is this way of sorting using Bits better (no Divisions and Modulo ) or the Common method is better ??

I also got WA

AC after memset

I implement Prim's algorithm with priority queue, and I got accepted in problem CSTREET using the exact same algorithm

Suggested Topics

Topic Category Replies Views Activity
C and C++ 0 23 14d

Want to read more? Browse other topics in C and C++ or view latest topics.