P2403 [SDOI2010] 所驼门王的宝藏 题解

link T2 desu

宫殿是 $R \times C$ 的矩阵，有 $N$ 个藏宝宫室，每间藏宝宫室有一扇传送门，类型为：

1. 横天门：可传送到同行的任一宫室
2. 纵霓门：可传送到同列的任一宫室
3. 任意门：可传送到周围 8 格中任一存在的宫室

Henry 可以用便携门从任意宫室进入，在任意宫室结束，但只允许进出一次。宫内传送门可无限次使用，宫室可重复访问。

目标：安排一条路线，使经过的不同藏宝宫室数量最多。

---

不用想，这道题肯定就是建完图后，问题变化为：求最多一次能经过的点的数量，点可以重复经过，但只计算一次。缩点跑 dp 统计最大值即可。

那么问题在于这个图该怎么建出来。

很显然一种非常暴力的做法就是对每个点考虑其能访问到的点然后对它连边。但是这样复杂度瓶颈在于横向传送门和竖向传送门。

考虑一个横行有 $k$ 个横向传送门，按照这样建图的复杂度为 $O(k^2)$。

但是真的需要这么多吗？

不妨令其中一个横向传送门作为这一行的 master。显然，master 自身需要往其他点连边。

而其他非 master 的横向传送门先经过 master 再访问其他传送门，这样就可以省下极大空间。

（如果没有横向传送门，那么针对这一横行的讨论是没有意义的）

可以保证这样的建图方式仍然能确保缩点正确。

那么现在的建图复杂度就是 $O(4(x+y)+8z)$，其中 $x+y$ 表示横竖传送门的数量，$z$ 表示“扫雷门”的数量。（很粗略的估计）

然后再建一个源点和汇点就可以 dp 了。

code:

int n,r,c;
struct Point{
	int x,y,col;
	int id;
	Point(){}
	Point(int x,int y,int col):x(x),y(y),col(col){}
	Point(int x,int y,int col,int id):x(x),y(y),col(col),id(id){}
	inline bool operator < (Point b)const{
		return (x==b.x)?((y==b.y)?(col<b.col):(y<b.y)):(x<b.x);
	}
}a[maxn];

set<Point> s;
unordered_map<int,vector<int> > line,column;
void input(){
	n=read();r=read();c=read();
	for(int i=1;i<=n;++i){
		int x=read(),y=read(),col=read();
		a[i]=Point(x,y,col,i);
		s.insert(Point(x,y,col,i));
		line[x].emplace_back(i);
		column[y].emplace_back(i);
	}
}

vector<int> edge[maxn];

void build_samexy(){
	for(auto p: line){
		int x=p.first;
		auto pts=&p.second;
		sort(pts->begin(),pts->end(),[](int x,int y){return a[x].y<a[y].y;});
		for(auto p: *pts){
			if(a[p].col!=1) continue;
			for(auto pp: *pts){
				if(p==pp) continue;
				edge[p].emplace_back(pp);
				if(a[pp].col==1) edge[pp].emplace_back(p);
			}
			break;
		}
	}
	for(auto p: column){
		int y=p.first;
		auto pts=&p.second;
		sort(pts->begin(),pts->end(),[](int x,int y){return a[x].x<a[y].x;});
		for(auto p: *pts){
			if(a[p].col!=2) continue;
			for(auto pp: *pts){
				if(p==pp) continue;
				edge[p].emplace_back(pp);
				if(a[pp].col==2) edge[pp].emplace_back(p);
			}
			break;
		}
	}
}

int f[8][2]={{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};
void build_8(){
	for(int i=1;i<=n;++i){
		if(a[i].col!=3) continue;
		int x=a[i].x,y=a[i].y;
		for(auto dt: f){
			int tx=x+dt[0],ty=y+dt[1];
			auto p=s.lower_bound(Point(tx,ty,0));
			if((*p).x==tx&&(*p).y==ty){
				edge[i].emplace_back((*p).id);
			}
		}
	}
}

void build_edge(){
	for(int i=1;i<=n;++i){
		edge[n+1].emplace_back(i);
		edge[i].emplace_back(n+2);
	}
	build_samexy();
	build_8();
}

int idx;
int dfn[maxn],low[maxn],insta[maxn];
int scccnt,inscc[maxn];
stack<int> sta;
void dfs(int x){
	dfn[x]=low[x]=++idx;
	sta.push(x);
	insta[x]=1;
	for(auto y: edge[x]){
		if(!dfn[y]){
			dfs(y);
			low[x]=min(low[x],low[y]);
		}
		else if(insta[y]){
			low[x]=min(low[x],dfn[y]);
		}
	}
	if(dfn[x]==low[x]){
		++scccnt;
		while(sta.size()&&sta.top()!=x){
			int p=sta.top();
			inscc[p]=scccnt;
			insta[p]=0;
			sta.pop();
		}
		inscc[x]=scccnt;
		insta[x]=0;
		sta.pop();
	}
}

vector<int> g[maxn];
int val[maxn],indu[maxn];
void rebuild_edge(){
	for(int i=1;i<=n+2;++i){
		int in=inscc[i];
		val[in]++;
		for(auto u: edge[i]){
			int inu=inscc[u];
			if(inu==in) continue;
			g[in].emplace_back(inu);
			indu[inu]++;
		}
	}
}

ll dp[maxn];
queue<int> que;
void solve(int st){
	que.push(st);
	dp[st]=val[st];
	while(que.size()){
		int x=que.front();
		que.pop();

		for(auto y: g[x]){
			dp[y]=max(dp[y],dp[x]+val[y]);
			--indu[y];
			if(indu[y]==0) que.push(y);
		}
	}
}

int main(){
	input();
	build_edge();
	dfs(n+1);
	rebuild_edge();
	solve(inscc[n+1]);
	printf("%lld",dp[inscc[n+2]]-2);
	return 0;
}

嗯非常史的实现。

sub