博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
[POI2018]Powódź
阅读量:6669 次
发布时间:2019-06-25

本文共 1337 字,大约阅读时间需要 4 分钟。

题目大意:

  一个$n\times m(nm\le5\times10^5)$的网格图,每个格子间有一个给定高度的挡板,每个格子的水位是$0\sim h(h\le10^9)$之间的一个整数。问总共有多少种可能的水位情况。

思路:

  建立Kruskal重构树,实点代表原图中的格点,虚点代表若干个格点水位越过挡板进行合并后形成的新连通块。求出每个点所代表连通块的水位最大值$max[i]$和最小值$min[i]$,根结点的$max$值为$h$。进行树形DP。转移方程$f[i]=f[ch[i][0]]\times f[ch[i][1]]+max[i]-min[i]+1$。

1 #include
2 #include
3 #include
4 #include
5 #include
6 typedef long long int64; 7 class MMapInput { 8 private: 9 char *buf,*p;10 int size;11 public:12 MMapInput() {13 register int fd=fileno(stdin);14 struct stat sb;15 fstat(fd,&sb);16 size=sb.st_size;17 buf=reinterpret_cast
(mmap(0,size,PROT_READ,MAP_PRIVATE,fileno(stdin),0));18 p=buf;19 }20 char getchar() {21 return (p==buf+size||*p==EOF)?EOF:*p++;22 }23 };24 MMapInput mmi;25 inline int getint() {26 register char ch;27 while(!isdigit(ch=mmi.getchar()));28 register int x=ch^'0';29 while(isdigit(ch=mmi.getchar())) x=(((x<<2)+x)<<1)+(ch^'0');30 return x;31 }32 const int N=1e6,mod=1e9+7;33 int n,m,h,cnt,tot,max[N],min[N],ch[N][2],f[N];34 struct Edge {35 int u,v,w;36 bool operator < (const Edge &another) const {37 return w

 

转载于:https://www.cnblogs.com/skylee03/p/8711067.html

你可能感兴趣的文章
面试2
查看>>
国庆第三天如何避免无聊
查看>>
Java多线程之细说线程池
查看>>
【274】Python 相关问题
查看>>
Apple watch ,小米微信通知
查看>>
Django 时间与时区设置问题
查看>>
【WPF】TextBox样式重写注意事项
查看>>
ORA-01652: 无法通过 128 (在表空间 TEMP1 中) 扩展 temp 段
查看>>
PO审批问题-行接收后更改价格变为预审批
查看>>
jquery 实现checkbox全选功能,全不选功能.
查看>>
What is a Notch Filter?
查看>>
Matlab中二维统计分析图和三维立体图
查看>>
MapReduce新版客户端API源码分析
查看>>
使用ffmpeg实现合并多个音频为一个音频的方法
查看>>
Eclipse Plugin Installation and Windows User Access Control
查看>>
Rotating Sentences
查看>>
Zookeeper从入门到精通(开发详解,案例实战,Web界面监控)
查看>>
jQuery操作Select
查看>>
DotNetCore跨平台~Startup类的介绍
查看>>
企业架构,业务架构,数据架构
查看>>