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