题目大意:
一个$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 #include2 #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