[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。
集合和每個格子是否被清理用并查集來維護就可以了。
 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 struct node
 7 {
 8     int s,x,y;
 9 } city[1000001],maze[100001];
10 pair<int,int> set[1001][1001];
11 int dx[5]={0,1,-1,0,0};
12 int dy[5]={0,0,0,1,-1};
13 int n,m,a[1001][1001],tot,cnt,vis[1001][1001],ans;
14 bool cmp(node a,node b)
15 {
16     return (a.s<b.s);
17 }
18 pair<int,int> find(pair<int,int> x)
19 {
20     if (set[x.first][x.second]!=x) set[x.first][x.second]=find(set[x.first][x.second]);
21     return set[x.first][x.second];
22 }
23 void union_set(pair<int,int> x,pair<int,int> y)
24 {
25     x=find(x),y=find(y);
26         set[x.first][x.second]=y;
27         vis[y.first][y.second]|=vis[x.first][x.second];
28 }
29 void exam(int x,int y)
30 {
31     for(int i=1;i<=4;i++)
32     {
33         int tx=x+dx[i], ty=y+dy[i];
34         if(tx<=0||ty<=0||tx>m||ty>n) continue;
35         if(a[tx][ty]>a[x][y]) continue;
36         union_set(make_pair(x, y), make_pair(tx, ty));
37     }
38 }
39 int main()
40 {
41     int i,j;
42     cin>>n>>m;
43     for (i=1; i<=n; i++)
44     {
45         for (j=1; j<=m; j++)
46         {
47             scanf("%d",&a[i][j]);
48             if (a[i][j]<=0)
49             {
50                 a[i][j]=-a[i][j];
51             }
52             else
53             {
54                 city[++tot]=(node){a[i][j],i,j};
55             }
56             maze[++cnt]=(node){a[i][j],i,j};
57             set[i][j]=make_pair(i,j);
58         }
59     }
60     sort(maze+1,maze+cnt+1,cmp);
61     sort(city+1,city+tot+1,cmp);
62     for (i=1; i<=tot; i++)
63     {
64         for (j=1; j<=cnt,city[i].s>=maze[j].s; j++)
65         {
66             exam(maze[j].x,maze[j].y);
67             pair<int,int> x=find(make_pair(city[i].x,city[i].y));
68             if (vis[x.first][x.second]==0)
69             {
70                 ans++;
71                 vis[x.first][x.second]=1;
72             }
73         }
74     }
75     cout<<ans;
76 }

?

轉載于:https://www.cnblogs.com/Y-E-T-I/p/7221242.html

本文來自互聯網用戶投稿,該文觀點僅代表作者本人,不代表本站立場。本站僅提供信息存儲空間服務,不擁有所有權,不承擔相關法律責任。
如若轉載,請注明出處:http://www.pswp.cn/news/253949.shtml
繁體地址,請注明出處:http://hk.pswp.cn/news/253949.shtml
英文地址,請注明出處:http://en.pswp.cn/news/253949.shtml

如若內容造成侵權/違法違規/事實不符,請聯系多彩編程網進行投訴反饋email:809451989@qq.com,一經查實,立即刪除!

相關文章

LOAM_velodyne學習(二)

LaserOdometry 這一模塊&#xff08;節點&#xff09;主要功能是&#xff1a;進行點云數據配準&#xff0c;完成運動估計 利用ScanRegistration中提取到的特征點&#xff0c;建立相鄰時間點云數據之間的關聯&#xff0c;由此推斷lidar的運動。我們依舊從主函數開始&#xff1…

戶外穿越

晚上很早就睡了&#xff0c;并且&#xff0c;太過激動&#xff0c;所以早上四點五十分就被驚醒&#xff0c;然后到早上鬧鐘響。 早上匆匆忙吃過早餐&#xff0c;就趕去坐車&#xff0c;到登山之前&#xff0c;坐了大巴車&#xff0c;又坐了景區的車&#xff0c;景區的路是山路十…

【oracle】關于創建表時用default指定默認值的坑

剛開始學create table的時候沒注意&#xff0c;學到后面發現可以指定默認值。于是寫了如下語句&#xff1a; 當我查詢的時候發現&#xff0c;查出來的結果是這樣的。。 很納悶有沒有&#xff0c;我明明指定默認值了呀&#xff0c;為什么創建出來的表還是空的呢&#xff1f;又跑…

Makefile中用宏定義進行條件編譯(gcc -D)/在Makefile中進行宏定義-D

在源代碼里面如果這樣是定義的&#xff1a; #ifdef MACRONAME //可選代碼 #endif 那在makefile里面 gcc -D MACRONAMEMACRODEF 或者 gcc -D MACRONAME 這樣就定義了預處理宏&#xff0c;編譯的時候可選代碼就會被編譯進去了。 對于GCC編譯器&#xff0c;有如下選項&…

python安裝與配置

首先下載python地址&#xff1a; https://www.python.org/downloads/release/python-361/下載頁面中有多個版本&#xff1a; web-based installer 是需要通過聯網完成安裝的 executable installer 是可執行文件(*.exe)方式安裝 embeddable zip file 嵌入式版本&#xff0c;可…

[OpenGL ES 03]3D變換:模型,視圖,投影與Viewport

[OpenGL ES 03]3D變換&#xff1a;模型&#xff0c;視圖&#xff0c;投影與Viewport 羅朝輝 (http://blog.csdn.net/kesalin) 本文遵循“署名-非商業用途-保持一致”創作公用協議 系列文章&#xff1a;[OpenGL ES 01]OpenGL ES之初體驗[OpenGL ES 02]OpenGL ES渲染管線與著色器…

LOAM_velodyne學習(三)

終于到第三個模塊了&#xff0c;我們先來回顧下之前的工作&#xff1a;點云數據進來后&#xff0c;經過前兩個節點的處理可以完成一個完整但粗糙的里程計&#xff0c;可以概略地估計出Lidar的相對運動。如果不受任何測量噪聲的影響&#xff0c;這個運動估計的結果足夠精確&…

監控視頻線種類 視頻信號傳輸介紹及各種視頻接口的傳輸距離

一.視頻信號接口 監控視頻線種類介紹&#xff1a; 按照材料區分有SYV及SYWV兩種&#xff0c;絕緣層的物理材料結構不同&#xff0c;SYV是實心聚乙烯電纜&#xff0c;SYWV是高物理發泡電纜&#xff0c;物理發泡電纜傳輸性能優于聚乙烯。 S--同軸電纜 Y--聚乙烯 V--聚氯乙烯 W…

免費節假日API 更新新功能了 新增農歷信息返回

感謝大家對免費節假日API的支持.最近看了別家的api于是增加了一些新功能即獲取日期的農歷信息. 這個新功能還處于測試階段如有問題歡迎反饋 檢查一個日期是詳細信息 https://tool.bitefu.net/jiari/?d20180101&info1 返回值 {"status": 1,"type": 1,…

新手算法學習之路----二叉樹(二叉樹最大路徑和)

摘抄自&#xff1a;https://segmentfault.com/a/1190000003554858#articleHeader2 題目&#xff1a; Given a binary tree, find the maximum path sum. The path may start and end at any node in the tree. For example: Given the below binary tree, 1/ \2 3Return 6. 思…

Ajax工作原理

詳見&#xff1a;http://blog.yemou.net/article/query/info/tytfjhfascvhzxcyt238 在這篇文章中&#xff0c;我將從10個方面來對AJAX技術進行系統的講解。 1、ajax技術的背景 不可否認&#xff0c;ajax技術的流行得益于google的大力推廣&#xff0c;正是由于google earth、go…

各種視頻信號格式及端子介紹/VGA DVI HDMI區別

視頻信號是我們接觸最多的顯示信號&#xff0c;但您并不一定對各種視頻信號有所了解。因為國內用到的視頻信號格式和端子非常有限&#xff0c;一般就是復合視頻和S端子&#xff0c;稍高級一些的就是色差及VGA。對于那些經常接觸國外電器和二手設備的朋友&#xff0c;就會遇到各…

LOAM_velodyne學習(四)

TransformMaintenance 來到了最后一個模塊&#xff0c;代碼不是很長&#xff0c;我們在看完代碼之后&#xff0c;再詳細說明這個模塊的功能 依然主函數開始 int main(int argc, char** argv) {ros::init(argc, argv, "transformMaintenance");ros::NodeHandle nh;…

PHP數據庫類

<?phpclass Db{//私有靜態屬性存儲實例化對象自身private static $instance;//存儲PDO類的實例化private $pdo;//PDOStatement類private $stmt;//禁止外部實例化對象&#xff0c;鏈接數據庫private function __construct($config,$port,$charset){try{$this->pdo new P…

oracle參數文件、控制文件、數據文件、日志文件的位置及查詢方法

參數文件&#xff1a;所有參數文件一般在 $ORACLE_HOME/dbs 下 sqlplus查詢語句&#xff1a;show parameter spfile; 網絡連接文件&#xff1a; $ORACLE_HOME/dbs/network/admin 目錄中 控制文件&#xff1a;select * from v$controlfile; 數據文件&#xff1a;一般在oracleda…

Bishops Alliance—— 最大上升子序列

原題鏈接&#xff1a;http://codeforces.com/gym/101147/problem/F 題意&#xff1a;n*n的棋盤&#xff0c;給m個主教的坐標及其私有距離p&#xff0c;以及常數C&#xff0c;求位于同一對角線上滿足條件&#xff1a;dist(i, j) > p[i]^2 p[j]^2 C 的主教集合的元素個數最…

LeGO-LOAM學習

前言 在學習了LOAM之后&#xff0c;了解到LeGO-LOAM&#xff08;面向復雜情況的輕量級優化地面的雷達里程計&#xff09;&#xff0c;進行了一個學習整理。 Github&#xff1a;https://github.com/RobustFieldAutonomyLab/LeGO-LOAM 論文&#xff1a;https://github.com/Robu…

char data[0]用法總結

struct MyData { int nLen; char data[0]; }; 開始沒有理解紅色部分的內容&#xff0c;上網搜索下&#xff0c;發現用處很大&#xff0c;記錄下來。 在結構中&#xff0c;data是一個數組名&#xff1b;但該數組沒有元素&#xff1b;該數組…

(一)低功耗設計目的與功耗的類型

一、低功耗設計的目的 1.便攜性設備等需求 電子產品在我們生活中扮演了極其重要的作用&#xff0c;便攜性的電子設備便是其中一種。便攜性設備需要電池供電、需要消耗電池的能量。在同等電能提供下&#xff0c;低功耗設計的產品就能夠工作更長的時間。時間的就是生命&#xff…

(轉)徹底學會使用epoll(一)——ET模式實現分析

注&#xff1a;之前寫過兩篇關于epoll實現的文章&#xff0c;但是感覺懂得了實現原理并不一定會使用&#xff0c;所以又決定寫這一系列文章&#xff0c;希望能夠對epoll有比較清楚的認識。是請大家轉載務必注明出處&#xff0c;算是對我勞動成果的一點點尊重吧。另外&#xff0…