#include <iostream>
using namespace std;

struct gather
{
	int p;
	int rank;
};

gather* makegather(int len)
{
	gather *a = new gather[len+1];
	for(int i=0; i<=len; i++)
		a[i].p = a[i].rank = 0;
	return a;
}

int find(gather* arr, int x)
{
	int root,y,t;
	y = x;
	while(arr[y].p != 0)
	{
		y = arr[y].p;
	}
	root = y;
	y = x;
	while(arr[y].p != 0)
	{
		t = arr[y].p;
		arr[y].p = root;
		y = t;
	}
	return root;
}

void unio(gather *arr,int x, int y)
{
	x = find(arr,x);
	y = find(arr,y);

	if(arr[x].rank <= arr[y].rank)
	{
		arr[x].p = y;
		if(arr[x].rank == arr[y].rank)
			arr[y].rank++;
	}
	else arr[y].p = x;
}

struct road
{
	int distance;
	int a,b;
};


void merge(road* arr,int a, int k, int b)
{
	int i,j,point;
	road *buffer = new road[b-a+1];
	
	i=a; j=k+1; point=0;
	while(i<=k && j<=b)
	{
		if(arr[i].distance < arr[j].distance)
			buffer[point++] = arr[i++];		
		else 
			buffer[point++] = arr[j++];	
	}
	if(i == k+1)
		for(;j<=b;j++)
			buffer[point++]=arr[j];
	else
		for(;i<=k;i++)
			buffer[point++]=arr[i];

	for(i=a,point=0;i<=b;i++)
		arr[i] = buffer[point++];

}

void busort(road* arr,int len)
{
	int width;
	int i;
	width = 2;
	int a,b;

	while(width/2 < len)
	{
		for(i=0; i<len; i+=width)
		{
			a = i;
			b = i+width-1;
			b = b<len-1?b:len-1;
			merge(arr,a,(a+b)/2,b);
		}	
		width = width*2;
	}
}

int main()
{
road *roadlist;
int *map;
gather *arr;

int city;
int connect;
int i,j;
int a,b;
int dif;
int point;
int llen;
int cost;

cin>>city;

//initial map,arr,dif;
map = new int[city*city];
arr = makegather(city);
dif = city;

for(i=0;i<city;i++)
	for(j=0;j<city;j++)
		cin>>map[i*city + j];

//procede existing connect
cin>>connect;
for(i=0;i<connect;i++)
{
	cin>>a>>b;
	map[(a-1)*city + b-1] = map[(b-1)*city + a-1] = 0;
	
	if(find(arr,a) != find(arr,b))
	{
		unio(arr,a,b);
		dif--;
	}

}

//ranke roadlist
roadlist = new road[city*(city-1)/2 - connect];
point = 0;
for(i=0;i<city-1;i++)
for(j=i+1;j<city;j++)
{
	if(map[i*city + j] != 0)
	{roadlist[point].distance = map[i*city + j];
	roadlist[point].a = i+1;
	roadlist[point].b = j+1;
	point++;}
}

if(point != city*(city-1)/2 - connect)
{cout<<"point error!"<<endl; exit(0);}

busort(roadlist,point);
llen = point;

//caculate the minix cost
cost = 0;
for(point=0; point<llen; point++)
{
	if(find(arr,roadlist[point].a) != find(arr,roadlist[point].b))
	{
		unio(arr,roadlist[point].a,roadlist[point].b);
		dif--;
		cost += roadlist[point].distance;
		point++;
		if(dif == 1) break;
	}
}


//out put
cout<<cost<<endl;





return 1;}

• Re:牛人来看看吧....WA了很久 (30) csjxl 2008-09-15 20:37:37