HDU 2235

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

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

#include <iostream>
#include <cstdio>
#include <string.h>
#include <algorithm>
using namespace std;
const int maxn = ;
struct point{
int loca,H;
point( int a = ,int c = ){
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[]={ , , , - };
int yy[]={ , -, , };
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)==){ for( int i = ; i < n ; ++ i )
for( int j = ; j < m ; ++ j ){
per[ i * m + j ] = i * m + j ;
map[ i ][ j ].num = ;
scanf("%d",&map[i][j].H);
hight[ i * m + j ]= point( i * m + j , map[ i ][ j ].H );
mark[ i ][ j ] = false;
}
__int64 ans = ;
sort( hight , hight + n*m );
for( int i = ; 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 = ; j< ; ++ j ){
int x = Tx + xx[ j ];
int y = Ty + yy[ j ];
if( x < || y < || 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 != ){
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 == ) {
falg = true ;
per[ fa ] = hight[ i ].loca;
}
}
if( falg ) map[ Tx ][ Ty ].num = ;
}
printf("%I64d\n",ans);
}
return ;
}
上一篇:用opencv实现工控机的开机录像


下一篇:MyBatis源码分析(一)开篇