这题说的是给了一个 平面 然后又很多的长方体柱子 问这个 容器的 容积是什么,
排序后 然后 进行 并查集 判断是否 可以有比他小的高度依靠他算体积，通过并查集去判断他的子集的个数。
#include <iostream> #include <cstdio> #include <string.h> #include <algorithm> using namespace std; const int maxn = 1001 ; struct point{ int loca,H; point( int a = 0 ,int c = 0 ){ loca = a ; H = c ; } bool operator < ( const point &A ) const { return H < A.H||(H==A.H&&loca<A.loca) ; } }hight[ maxn * maxn ]; struct node{ int num , H ; }map[ maxn ][ maxn ]; int per[ maxn * maxn ],n,m; int xx[]={ 0 , 0, 1, -1 }; int yy[]={ 1 , -1, 0, 0 }; bool mark[ maxn ][ maxn ]; int F(int x){ if( x == per[x] ) return x ; per[ x ] = F( per[ x ] ); return per[ x ]; } int main() { while(scanf("%d%d",&n,&m)==2){ for( int i = 0 ; i < n ; ++ i ) for( int j = 0 ; j < m ; ++ j ){ per[ i * m + j ] = i * m + j ; map[ i ][ j ].num = 1 ; scanf("%d",&map[i][j].H); hight[ i * m + j ]= point( i * m + j , map[ i ][ j ].H ); mark[ i ][ j ] = false; } __int64 ans = 0; sort( hight , hight + n*m ); for( int i = 0 ; i < n*m ; ++ i ){ bool falg = false ; int Tx = hight[ i ].loca/m; int Ty = hight[ i ].loca%m; mark[Tx][Ty] = true; for( int j = 0 ; j< 4 ; ++ j ){ int x = Tx + xx[ j ]; int y = Ty + yy[ j ]; if( x < 0 || y < 0 || x >= n || y >= m ){ falg = true; continue; } int fa = F( x * m + y ); if( fa == hight[ i ].loca ) continue; int fx = fa / m; int fy = fa % m; if( mark[ fx ][ fy ] == true && map[ fx ][ fy ].num != 0 ){ ans += ( map[Tx][Ty].H - map[ fx ][ fy ].H ) * map[fx][fy].num; per[ fa ] = hight[ i ].loca ; map[ Tx ][ Ty ].num += map[ fx ][ fy ].num; } else if( map[ fx ][ fy ].num == 0 ) { falg = true ; per[ fa ] = hight[ i ].loca; } } if( falg ) map[ Tx ][ Ty ].num = 0; } printf("%I64d ",ans); } return 0; }