BZOJ1736 [Usaco2005 jan]The Wedding Juicer 婚宴的榨汁机

从外面一点一点往里面拓展(floodfill)，每次找出最小的一个点，计算它对答案的贡献就好了。。。

找最小的点的话，直接pq就行

 /**************************************************************

     Problem: 1736

     User: rausen

     Language: C++

     Result: Accepted

     Time:196 ms

     Memory:2116 kb

 ****************************************************************/

 #include <cstdio>

 #include <queue>

 using namespace std;

 typedef long long ll;

 const int N = ;

 const int dx[] = {, , , -};

 const int dy[] = {, -, , };

 inline int read();

 struct data {

     int x, y, h;

     data(int _x = , int _y = , int _h = ) : x(_x), y(_y), h(_h) {}

     inline bool operator < (const data &d) const {

         return h > d.h;

     }

 };

 int n, m;

 int mp[N][N], v[N][N];

 priority_queue <data> h;

 inline ll work(){

     ll res = ;

     int x, y, k;

     data now;

     while (!h.empty()) {

         now = h.top(), h.pop();

         for (k = ; k < ; ++k) {

             x = now.x + dx[k], y = now.y + dy[k];

             if (x <=  || y <=  || x > n || y > m || v[x][y]) continue;

             v[x][y] = ;

             if (mp[x][y] < now.h)

                 res += now.h - mp[x][y], mp[x][y] = now.h;

             h.push(data(x, y, mp[x][y]));

         }

     }

     return res;

 }

 int main() {

     int i, j;

     m = read(), n = read();

     for (i = ; i <= n; ++i)

         for (j = ; j <= m; ++j) mp[i][j] = read();

     for (i = ; i <= n; ++i)

         for (j = ; j <= m; ++j)

             if (i ==  || j ==  || i == n || j == m)

                 h.push(data(i, j, mp[i][j])), v[i][j] = ;

     printf("%lld\n", work());

     return ;

 }

 inline int read() {

     static int x;

     static char ch;

     x = , ch = getchar();

     while (ch < '' || '' < ch)

         ch = getchar();

     while ('' <= ch && ch <= '') {

         x = x *  + ch - '';

         ch = getchar();

     }

     return x;

 }