[POI2007]POW-The Flood

題目描述

給定一張地勢圖，所有的點都被水淹沒，現在有一些關鍵點，要求放最少的水泵使所有關鍵點的水都被抽干

輸入輸出格式

輸入格式：

In the first line of the standard input there are two integers??and?, separated by a single space,. The following??lines contain the description of the map. The?'th linedescribes the?'th row ofunitary squares in the map. It contains??integers?, separated by single spaces,,?.

The number??describes the?'th square of the ![](http://main.edu.pl/images/OI14/pow-en-tex.14.pn…

輸出格式：

Your programme should write out one integer to the standard output - the minimum number of pumpsneeded to drain Byteburg.

輸入輸出樣例

輸入樣例#1：

6 9
-2 -2 -1 -1 -2 -2 -2 -12 -3
-2 1 -1 2 -8 -12 2 -12 -12
-5 3 1 1 -12 4 -6 2 -2
-5 -2 -2 2 -12 -3 4 -3 -1
-5 -6 -2 2 -12 5 6 2 -1
-4 -8 -8 -10 -12 -8 -6 -6 -4

輸出樣例#1：

2
我們首先考慮如果在格子 a 修建一個抽水機，在什么情況下格子 b 的水也可以被抽干。
我們可以發現當且僅當存在一條從 a 到 b 的路徑，中間經過的抽水機（包括 a）的高度都不大于 b 的高度。
即h[b]>=max(h[i])
因此我們可以考慮把所有格子的高度從小到大排序，我們把每一個格子建成一個集合。
然后按照海拔高度從小到大掃描格子，對于當前的格子 i，我們找到所有與 i 相鄰并且海拔高度不大于格子 i 的格子，
我們發現如果這些格子中的任意一個洪水要是被解決了，那么格子 i 的洪水也可以被解決，所以我們合并這些格子。
對于當前的格子 i，如果它必須被清理且與它相鄰的格子集合中沒有任何一個被清理，我們則把這個集合的清理狀態標記為真，然后答案加 1。
集合和每個格子是否被清理用并查集來維護就可以了。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct node
{
    int s,x,y;
} city[1000001],maze[100001];
pair<int,int> set[1001][1001];
int dx[5]={0,1,-1,0,0};
int dy[5]={0,0,0,1,-1};
int n,m,a[1001][1001],tot,cnt,vis[1001][1001],ans;
bool cmp(node a,node b)
{
    return (a.s<b.s);
}
pair<int,int> find(pair<int,int> x)
{
    if (set[x.first][x.second]!=x) set[x.first][x.second]=find(set[x.first][x.second]);
    return set[x.first][x.second];
}
void union_set(pair<int,int> x,pair<int,int> y)
{
    x=find(x),y=find(y);
        set[x.first][x.second]=y;
        vis[y.first][y.second]|=vis[x.first][x.second];
}
void exam(int x,int y)
{
    for(int i=1;i<=4;i++)
    {
        int tx=x+dx[i], ty=y+dy[i];
        if(tx<=0||ty<=0||tx>m||ty>n) continue;
        if(a[tx][ty]>a[x][y]) continue;
        union_set(make_pair(x, y), make_pair(tx, ty));
    }
}
int main()
{
    int i,j;
    cin>>n>>m;
    for (i=1; i<=n; i++)
    {
        for (j=1; j<=m; j++)
        {
            scanf("%d",&a[i][j]);
            if (a[i][j]<=0)
            {
                a[i][j]=-a[i][j];
            }
            else
            {
                city[++tot]=(node){a[i][j],i,j};
            }
            maze[++cnt]=(node){a[i][j],i,j};
            set[i][j]=make_pair(i,j);
        }
    }
    sort(maze+1,maze+cnt+1,cmp);
    sort(city+1,city+tot+1,cmp);
    for (i=1; i<=tot; i++)
    {
        for (j=1; j<=cnt,city[i].s>=maze[j].s; j++)
        {
            exam(maze[j].x,maze[j].y);
            pair<int,int> x=find(make_pair(city[i].x,city[i].y));
            if (vis[x.first][x.second]==0)
            {
                ans++;
                vis[x.first][x.second]=1;
            }
        }
    }
    cout<<ans;
}

?