首页 > 代码库 > HDU 2235
HDU 2235
这题说的是给了一个 平面 然后又很多的长方体柱子 问这个 容器的 容积是什么,
排序后 然后 进行 并查集 判断是否 可以有比他小的高度依靠他算体积,通过并查集去判断他的子集的个数。
#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;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。