【bzoj5101】[POI2018]Powód 并查集
查集 PoW
2023-09-11 14:22:39 时间
题目描述
在地面上有一个水箱,它的俯视图被划分成了n行m列个方格,相邻两个方格之间有一堵厚度可以忽略不计的墙,水箱与外界之间有一堵高度无穷大的墙,因此水不可能漏到外面。已知水箱内每个格子的高度都是[0,H]之间的整数,请统计有多少可能的水位情况。因为答案可能很大,请对10^9+7取模输出。两个情况不同当且仅当存在至少一个方格的水位在两个情况中不同。
输入
第一行包含三个正整数n,m,H(n*m<=500000,1<=H<=10^9)。
接下来n行,每行m-1个整数a[i][j](1<=a[i][j]<=H),表示(i,j)和(i,j+1)之间的墙的高度。
接下来n-1行,每行m个整数b[i][j](1<=b[i][j]<=H),表示(i,j)和(i+1,j)之间的墙的高度。
输出
输出一行一个整数,即方案数模10^9+7的结果。
样例输入
3 2 2
1
1
1
1 2
1 1
样例输出
65
题解
并查集
首先容易发现,所有方格的连接是一个类似于最小生成树的过程。
因此我们先把每个隔板按照高度从小到大排序,然后一个一个加入。
对于每一个连通块,维护其:连通的最小高度(即最后加的一条边)$last[i]$ 、和连通之前的方案数 $v[i]$ 。
那么高度为 $z$ 时合并两个连通块 $x$ 和 $y$ ,形成新连通块的 $last$ 等于 $z$,方案数等于 $(v[x]+z-last[x])(v[y]+z-last[y])$ 。
如果最终的连通块为 $i$ ,则最后的答案即为 $v[i]+H-last[i]$ 。
时间复杂度 $O(nm\log n)$
#include <cstdio> #include <algorithm> #define N 500010 #define mod 1000000007 #define pos(i , j) ((i - 1) * m + j) using namespace std; typedef long long ll; struct data { int x , y , z; data() {} data(int a , int b , int c) {x = a , y = b , z = c;} bool operator<(const data &a)const {return z < a.z;} }a[N << 1]; int f[N] , last[N] , tot; ll v[N]; int find(int x) { return x == f[x] ? x : f[x] = find(f[x]); } int main() { int n , m , k , i , j , x , y; scanf("%d%d%d" , &n , &m , &k); for(i = 1 ; i <= n ; i ++ ) for(j = 1 ; j < m ; j ++ ) scanf("%d" , &x) , a[++tot] = data(pos(i , j) , pos(i , j + 1) , x); for(i = 1 ; i < n ; i ++ ) for(j = 1 ; j <= m ; j ++ ) scanf("%d" , &x) , a[++tot] = data(pos(i , j) , pos(i + 1 , j) , x); sort(a + 1 , a + tot + 1); for(i = 1 ; i <= n * m ; i ++ ) f[i] = i , last[i] = -1; for(i = 1 ; i <= tot ; i ++ ) { x = find(a[i].x) , y = find(a[i].y); if(find(x) != find(y)) v[y] = (v[y] + a[i].z - last[y]) * (v[x] + a[i].z - last[x]) % mod , last[y] = a[i].z , f[x] = y; } x = find(1); printf("%lld\n" , (v[x] + k - last[x]) % mod); return 0; }
相关文章
- docker node rm节点报错node ... ... is not down and can't be removed 问题的处理技巧
- What's vmware horizon client?
- Web Api调用遇到错误提示System.Web.HttpException (0x80004005): The controller for path '' was not found or does not implement IController.
- What does an 'r' represent before a string in python? [duplicate]
- [转载]python中if name == 'main':的作用和原理
- React antd嵌入百度编辑器(css加载不到等问题,'offsetWidth' of null)
- Ionic Framework - Getting 'ionic start [appName]' Working Behind a Proxy
- Uncaught SyntaxError: Unexpected token '<' (at 报错
- ASP.NET list<object> OBJECT.clean()会清空session['OBJECT']的值的问题
- 使用navicat连接mysql连接错误:Lost connection to Mysql server at 'waiting for initial communication packet'
- flink-sql-gateway:Caused by: org.apache.flink.table.api.NoMatchingTableFactoryException: Could not find a suitable table factory for 'org.apache.flink.table.factories.CatalogFactory' in the classpath.
- Managing Large State in Apache Flink®: An Intro to Incremental Checkpointing
- 北电之死:谁谋杀了华为的对手?——银湖资本(Silver Lake)董事总经理爱德华·詹德出任CEO,既不了解华为,也不重视中国,直截了当地否决了收购华为
- JSONUtil.bean2Json()报Property 'key' of class has no read method. SKIPPED的问题处理
- vagrant yii2 Exception 'yiidbException' with message 'SQLSTATE[HY000] [2002]
- BSS Audio® Introduces Full-Bandwidth Acoustic Echo Cancellation Algorithm for Soundweb London Conferencing Processors
- Dell'Oro预测:2020年5G RAN收入将远超2010年4G RAN收入水平
- D - The Frog's Games (二分)