首页 > 代码库 > HDU 2235

HDU 2235

2024-07-08 07:54:53   220人阅读

这题说的是给了一个 平面 然后又很多的长方体柱子 问这个 容器的 容积是什么,

排序后 然后 进行 并查集 判断是否 可以有比他小的高度依靠他算体积，通过并查集去判断他的子集的个数。

#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\n",ans);    }    return 0;}
View Code

 


联系
我们