|
|
Posted on 2008-07-30 12:23 Hero 閱讀(306) 評論(0) 編輯 收藏 引用 所屬分類: 代碼如詩－－ACM
/*
ID: wangzha4
LANG: C++
TASK: fence6
*/
//利用floyed算法求最小環－－參見圖片的算法
/*
Executing
Test 1: TEST OK [0.000 secs, 2848 KB]
Test 2: TEST OK [0.011 secs, 2852 KB]
Test 3: TEST OK [0.000 secs, 2848 KB]
Test 4: TEST OK [0.000 secs, 2848 KB]
Test 5: TEST OK [0.011 secs, 2848 KB]
Test 6: TEST OK [0.000 secs, 2848 KB]
Test 7: TEST OK [0.000 secs, 2852 KB]
Test 8: TEST OK [0.011 secs, 2852 KB]
Test 9: TEST OK [0.000 secs, 2848 KB]
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#define llong unsigned long long
#define unint unsigned int
#define printline printf( "\n" )
double fmax( double a, double b )
{
if( a - b > 0 ) return a ;
else return b ;
}
double fmin( double a, double b )
{
if( a - b < 0 ) return a ;
else return b ;
}
int fmax( int a, int b )
{
if( a > b ) return a ;
else return b ;
}
int fmin( int a, int b )
{
if( a < b ) return a ;
else return b ;
}
int fpow( int a, int b )
{
int reval = 1 ;
for( int i=1; i<=b; i++ )
reval *= a ;
return reval ;
}
const int INF = 1000000 ;
const int size = 120 ;
int inn ; int out = INF ;
int edge[size][size] ;
int dist[size][size] ;
int flen[size] ;
int left[size][10] ;
int right[size][10] ;
bool inleft[size][size] = { false } ;
int flag[size] = {0} ;
int minCircle()
{//尋找最小環
for( int i=0; i<=inn; i++ ) for( int j=0; j<=inn; j++ )
dist[i][j] = edge[i][j] ;//dist數組初始化
int reval = INF ;
for( int k=1; k<=inn; k++ )
{//枚舉最大的點
for( int i=1; i<=left[k][0]; i++ ){//從最大點的左邊選出小于當前最大點的左節點
int curleft = left[k][i] ;
if( curleft < k ){
for( int j=1; j<=right[k][0]; j++ ){//從最大點的右邊選出小于當前最大點的右節點
int curright = right[k][j] ;
if( curright < k ){
reval = fmin( reval, dist[curleft][curright]+edge[curleft][k]+edge[k][curright] ) ;
}//構成環
}
}
}
for( int i=1; i<=inn; i++ ) for( int j=1; j<=inn; j++ )
if( i==j || i==k || j==k ) continue ;
else dist[i][j] = dist[j][i] = fmin( dist[i][j], dist[i][k]+dist[k][j] ) ;
}
return reval ;
}
int main()
{
freopen( "fence6.in", "r", stdin ) ;
freopen( "fence6.out","w",stdout ) ;
scanf( "%d",&inn ) ; int fnum ;
for( int i=1; i<=inn; i++ )
{
scanf( "%d",&fnum ) ;
scanf( "%d",&flen[fnum] ) ;
scanf( "%d %d",&left[fnum][0],&right[fnum][0] ) ;
for( int j=1; j<=left[fnum][0]; j++ ){
scanf( "%d",&left[fnum][j] ) ;
inleft[fnum][left[fnum][j]] = true ;
}
for( int j=1; j<=right[fnum][0]; j++ ){
scanf( "%d",&right[fnum][j] ) ;
}
}//data input
for( int i=0; i<=inn; i++ ){
for( int j=0; j<=inn; j++ ){
edge[i][j] = dist[i][j] = INF ;
}
}//edge init
for( int i=1; i<=inn; i++ )
{
for( int j=1; j<=left[i][0]; j++ )
edge[i][left[i][j]] = flen[i] + flen[left[i][j]] ;
for( int j=1; j<=right[i][0]; j++ )
edge[i][right[i][j]] = flen[i] + flen[right[i][j]] ;
}
out = minCircle() ;
printf( "%d\n",out/2 ) ;
return 0 ;
}
|