「THUSC 2012」水位 - 并查集+高精度

题目大意

    给出一个网格图，每个位置有一个地表高度，水面高度必须大于等于地表高度，且在$[0,m]$间，是个整数。
    水按照生活常识流动，如下图（地表高度/水面高度）中左图合法，右图不合法。

求合法的不同水位情况数。

---

题目分析

这题有一个很明显的状压动规做法。
因为将原图剖分成块，块与块只可能是包含或不相交关系，不可能是相交但不包含关系。
设$f[S]$表示集合$S$的方案数。
可以考虑从$f[S]$扩展到$f[S’]$（集合扩张），方案数累加。
也可以考虑将$f[S]$和$f[T]$合并，方案数累乘。
复杂度高且不好实现。

进一步我们考虑到状态没有必要显示设置出来，因为有明显的阶段顺序（从地表高度低的格子扩展到地表高度高的格子）。
故将每一个块用并查集表示，从水位低的往高的依次合并并查集，按照上面说的方式统计方案数即可。

注意需要高精度。

---

代码

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;

inline const int Get_Int() {
	int num=0,bj=1;
	char x=getchar();
	while(x<'0'||x>'9') {
		if(x=='-')bj=-1;
		x=getchar();
	}
	while(x>='0'&&x<='9') {
		num=num*10+x-'0';
		x=getchar();
	}
	return num*bj;
}

typedef long long LL;
struct BigInteger {
	const static int BASE=100000000,WIDTH=8;
	vector<LL>s;
	BigInteger() {
		*this=0;
	}
	BigInteger(const LL& num) {
		*this=num;
	}
	//赋值
	BigInteger operator = (LL num) {
		s.clear();
		do {
			s.push_back(num%BASE);
			num/=BASE;
		} while(num>0);
		return *this;
	}
	//+
	BigInteger operator + (BigInteger b) {
		BigInteger c;
		c.s.clear();
		LL g=0;
		for(int i=0; ; i++) {
			if(g==0&&i>=s.size()&&i>=b.s.size())break;
			LL x=g;
			if(i<s.size())x+=s[i];
			if(i<b.s.size())x+=b.s[i];
			c.s.push_back(x%BASE);
			g=x/BASE;
		}
		return c;
	}
	void operator += (BigInteger b) {
		*this=*this+b;
	}
	//*
	BigInteger operator * (const BigInteger& b) {
		BigInteger a=*this,c;
		c.s.resize(a.s.size()+b.s.size());
		for(int i=0; i<a.s.size(); i++)
			for(int j=0; j<b.s.size(); j++)c.s[i+j]+=a.s[i]*b.s[j];
		for(int i=0; i<c.s.size()-1; i++) {
			c.s[i+1]+=c.s[i]/BASE;
			c.s[i]%=BASE;
		}
		while(c.s.back()==0&&c.s.size()>1)c.s.pop_back();
		return c;
	}
	void operator *= (const BigInteger& b) {
		*this=*this*b;
	}
	friend ostream& operator << (ostream& output,const BigInteger& x) {
		output<<x.s.back();
		for(int i=x.s.size()-2; i>=0; i--) {
			char buf[20];
			sprintf(buf,"%08lld",x.s[i]);
			for(int j=0; j<strlen(buf); j++)output<<buf[j];
		}
		return output;
	}
};

const int maxn=105;
const int dx[]= {1,-1,0,0},dy[]= {0,0,1,-1};

int n,m,Height[maxn*maxn],father[maxn*maxn];
BigInteger ans[maxn*maxn];

int get_id(int x,int y) {
	return (x-1)*n+y;
}

int Get_Father(int x) {
	if(father[x]==x)return x;
	return father[x]=Get_Father(father[x]);
}

struct Point {
	int x,y,id;
	Point(int _x=0,int _y=0):x(_x),y(_y) {
		id=get_id(_x,_y);
	}
	bool operator < (const Point& b) const {
		return Height[id]<Height[b.id]||(Height[id]==Height[b.id]&&id<b.id);
	}
	bool inmap() {
		return x>=1&&x<=n&&y>=1&&y<=n;
	}
} P[maxn*maxn];

int main() {
	n=Get_Int();
	m=Get_Int();
	for(int i=1; i<=n; i++)
		for(int j=1; j<=n; j++) {
			Height[get_id(i,j)]=Get_Int();
			P[get_id(i,j)]=Point(i,j);
		}
	for(int i=1; i<=n*n; i++) {
		father[i]=i;
		ans[i]=1;
	}
	sort(P+1,P+n*n+1);
	for(int i=1; i<=n*n; i++)
		for(int d=0; d<4; d++) {
			Point Now=P[i];
			Point Next=Point(Now.x+dx[d],Now.y+dy[d]);
			if(!Next.inmap())continue;
			int fx=Get_Father(Now.id),fy=Get_Father(Next.id);
			if(fx!=fy&&Height[fx]>=Height[fy]) {
				ans[fy]+=Height[fx]-Height[fy];
				ans[fx]*=ans[fy];
				father[fy]=fx;
			}
		}
	int fx=Get_Father(1);
	ans[fx]+=m-Height[fx];
	cout<<ans[fx];
	return 0;
}