| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
2831 WA??用prim求最小生成树,然后每次替换再对ct检查!!#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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator