Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

2831 WA??用prim求最小生成树,然后每次替换再对ct检查!!

Posted by sail6 at 2006-08-24 11:01:26 on Problem 2831
#include<iostream.h>


struct edge
{
	int  fromvex ;
	int  endvex ;
	int  weight ;
} ;

struct Node
{
	
	int  fromvex ;
	int  endvex ;
	int  weight ;
} ;



const  int  maxEdgeNum = 1010;
Node node [ 1001 ] ;
typedef   edge edgeset [ 1001 ] ;

const  int  MaxvertexNum = 1001 ;

 typedef int  adjmatrix [ 1001 ] [ 1001 ] ;
adjmatrix  GA  ;
adjmatrix  GA1  ;

const int  Maxvalue = 1000001 ;


int Prim ( adjmatrix  GA , edgeset  &CT , int  n )
{
	int i , j , k , min , t , m , w ;
	for(i = 0 ; i < n - 1 ; i ++ )
	{
		CT [ i ] . fromvex = 0 ;
		CT [ i ] . endvex = i + 1 ;
		CT [ i ] . weight = GA [ 0 ] [ i + 1 ]  ;
	}
	for ( k = 1 ; k < n ; k ++ )
	{
		min =  Maxvalue ;
		m  =   k-1;
		for( j = k - 1 ; j < n - 1 ; j ++ )
		{
			if ( CT [j] . weight < min)
			{
				min = CT [j] . weight ;
				m = j ;
				
			}
		}
		edge  temp = CT [ k - 1 ] ;
		CT [ k - 1 ] = CT [ m ] ;
		CT [ m ] = temp ;
		j = CT [ k - 1 ] . endvex ;
		for ( i = k ; i < n -1 ; i ++ )
		{
			t = CT [i] . endvex ;
			w = GA [ j ] [ t ];
			if ( w < CT [ i ] .weight )
			{
				CT [ i ] .weight = w ;
				CT [ i ] .fromvex = j ;
			}
			
		}
		
	}
	
	
	return 0; 
}

edgeset  CT1  ;


int main ( )
{
	int  N , M , Q ;
	cin >> N >> M >> Q ;
	int  i , j ;
	int  a , b , c ;
	

	edgeset  CT ; 
	
	for ( i = 0 ; i < N ; i ++ )
	{
		for ( j = 0 ; j < N ; j ++ )
		{
			GA [ i ] [ j ] = Maxvalue ;
		}
		
	}
	
	for ( i = 0 ; i < M ; i ++ )
	{
		cin >> a >> b >> c ;
		node [ i ] . fromvex = a - 1 ;
		node [ i ] .endvex = b - 1 ;
		node [ i ]. weight = c ;
		//	cout << i << ' ' << node [ i ] . fromvex << ' ' << node [ i ] .endvex << ' ' << 	node [ i ]. weight << endl << endl ;
		
		if ( c < 	GA [ a - 1 ] [ b - 1 ] )
		{
			GA [ a - 1 ] [ b - 1 ] = c ;
			GA [ b - 1 ] [ a - 1] = c ;
		}
		
	}
	/*for ( i = 0 ; i < N ; i ++ )
	{
		for ( j = 0 ; j < N ; j ++ )
		{
			cout << GA [ i ] [ j ]<<' ';
		}
		cout<<endl;
	}
	*/
	Prim (   GA ,   CT , N ) ;
	//int weight1 = 0 , weight2 = 0 ;
	
	int  k , w ;
	edgeset  CT1 ; 
	
	for ( i = 0 ; i < Q ; i ++ )
	{
		for ( int ii = 0 ; ii < N ; ii ++ )
		{
			for ( j = 0 ; j < N ; j ++ )
			{
				 GA1 [ ii ] [ j ] =  GA [ ii ] [ j ] ;
			}
			//cout<<endl;
		}

		cin >> k >> w ;
		a = node [ k - 1 ] . fromvex ;
		b = node [ k - 1 ] . endvex ;
		
		GA1 [ a  ] [ b  ] = GA1 [ b ] [ a ] = w ;

	/*	for (  ii = 0 ; ii < N ; ii ++ )
		{
			for ( j = 0 ; j < N ; j ++ )
			{
				cout << GA1 [ ii ] [ j ]<<' ';
			}
			cout<<endl;
		}
		cout<<endl<<endl;*/
		Prim (   GA1 ,  CT1 , N ) ;

		int  flag = 0 ;
		for ( j = 0 ; j < N - 1 ; j ++ )
		{
			if ( a == CT1 [ j ].fromvex && b == CT1 [j].endvex && w == CT1 [ j ].weight )
			{
				flag=1;
				break;
			}
		}
		if ( flag==1 )
		{
			cout << "Yes" << endl ;
		}
		else
		{
				cout << "No" << endl ;
		}
	}
	
	return 0;
	
	
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator