夏晓光(loveJY)的博客

啊这

优化建图题调的时候一定要把整个图画出来然后自己慢慢看

还有就是图论中基础板子一定不能写错了

对于此题,我们建n+R+C个点

R:表示行电梯,乘上该电梯可以到达所有同一行的点

C:表示列电梯....

然后对于一个点i,如果是一二类边,我们就把另一类的电梯向他连边,并从该点向对应特征电梯连边!

最后还有第三类边,可以直接暴力,用一个map存一下每个点的pair即可!

时间复杂度O(nlogn),复杂度在于map

#include<bits/stdc++.h>
#define mkp(x,y) (make_pair(x,y))
const int MAXN = 5e5 + 7;
const int MAXM = 2e6 + 7;
using namespace std;
map<pair<int, int>, int> mp;
int n, R, C, T;
const int dx[] = {-1, -1, -1, 0, 0, 1, 1, 1};
const int dy[] = {-1, 0, 1, -1, 1, -1, 0, 1};
int H[MAXM], L[MAXM], in[MAXN], d[MAXN], first[MAXN];
int hd, que[MAXN], tl, dis[MAXN], fl[MAXN];
int ccnt2, exn;
int a[MAXN], S[MAXN];

struct rec {
	int nxt, to;
} e[MAXM];
struct NODE {
	int x, y, t;
} nd[MAXN];


inline void tpdp() {
	puts("In tpdp");
	for(int i = 1; i <= exn; ++i) {
		if(in[i] == 0) {
			que[tl++] = i;
			dis[i] = S[i];
			// printf("起点 :%d %d? %d\n",  i, S[i], in[i]);
		}
	}

	while(hd <= tl) {
		int u = que[hd];
		++hd;
		// printf("poor boy:%d?\n", u);
		for(int i = first[u]; i; i = e[i].nxt) {
			int v = e[i].to;
			in[v]--;
			// printf("update%d %d %d->\n", dis[u], dis[v], S[v]);
			dis[v] = max(dis[u] + S[v], dis[v]);
			if(!in[v]) {
				que[++tl] = v;
			}
		}
	}

	return ;
}
int ccnt, home[MAXN], nxt[MAXM], to[MAXM];
inline void ct(int x, int y) {
	ccnt++;
	nxt[ccnt] = home[x];
	home[x] = ccnt;
	to[ccnt] = y;
}

inline void ct2(int x, int y) {
	ccnt2++;
	e[ccnt2].nxt = first[x];
	first[x] = ccnt2;
	e[ccnt2].to = y;
	in[y]++;
}

int dfn[MAXN], low[MAXN], depp, st[MAXN], tp;
inline void tarjan(int u) {
	dfn[u] = ++depp;
	low[u] = dfn[u];
	st[++tp] = u;
	fl[u] = 1;
	// printf("now we in node:%d %d?\n", u, dfn[u]);
	for(int i = home[u]; i; i = nxt[i]) {
		int v = to[i];
		if(!dfn[v]) {
			tarjan(v);
			low[u] = min(low[u], low[v]);
		} else if(!fl[v])continue;
		low[u] = min(low[u], dfn[v]);
	}
	// printf("so the %d' low is %d?\n", u, low[u]);
	if(low[u] == dfn[u]) {
		exn++;
		while(st[tp] != u) {
			int v = st[tp];
			--tp;
			S[exn] += a[v];
			d[v] = exn;
			fl[v] = 0;
		}
		tp--;
		S[exn] += a[u];
		d[u] = exn;
		fl[u] = 0;
		// printf("%d?%d\n", tp, exn);
	}
	return ;
}

int main() {
	scanf("%d%d%d", &n, &R, &C);
	T = n;
	for(int i = 1; i <= n; ++i) {
		scanf("%d%d%d", &nd[i].x, &nd[i].y, &nd[i].t);
		if(!L[nd[i].y])L[nd[i].y] = ++T;
		if(!H[nd[i].x])H[nd[i].x] = ++T;
		// printf("%d %d\n", L[nd[i].y], H[nd[i].x]);
		if(nd[i].t == 1) {
			ct(H[nd[i].x], i);
			ct(i, H[nd[i].x]);
			ct(L[nd[i].y], i);//列只能被动接受
		}
		if(nd[i].t == 2) {
			ct(H[nd[i].x], i);//行只能被动接受
			ct(L[nd[i].y], i);
			ct(i, L[nd[i].y]);
		}
		if(nd[i].t == 3) {
			ct(H[nd[i].x], i);
			ct(L[nd[i].y], i);//都只能被迫接受
		}
		a[i] = 1;
		mp[mkp(nd[i].x, nd[i].y)] = i;
	}
	for(int i = 1; i <= n; ++i) {
		if(nd[i].t == 3) {
			for(int k = 0; k < 8; ++k) {
				int nx = dx[k] + nd[i].x;
				int ny = dy[k] + nd[i].y;
				// printf("%d %d?\n", nx, ny);
				if(mp.find(mkp(nx, ny)) != mp.end()) {
					// printf("U:%d?%d\n", nx, ny);
					ct(i, mp[mkp(nx, ny)]);
				}
			}
		}
	}
	for(int i = 1; i <= T; ++i) {
		if(!dfn[i])
			tarjan(i);
	}
	for(int u = 1; u <= T; ++u) {
		// printf("where is Kindom!:%d here %d have lots of %d\n", u, d[u], S[d[u]]);
		for(int i = home[u]; i; i = nxt[i]) {
			int v = to[i];
			if(d[u] == d[v])continue;
			// printf("I'm %d and belong to %d:edge to %d?\n", u, d[u], d[v]);
			ct2(d[u], d[v]);
		}
	}
	tpdp();
	int ans = 0;
	for(int i = 1; i <= exn; ++i) {
		// printf("%d %d\n", i, dis[i]);
		ans = max(ans, dis[i]);
	}
	printf("%d\n", ans);
	return 0;
}