题目大意：
#include <cstdio>
#include <queue>
#include <map>
const int N = 100005, M = 1000005;
const int dx[8] = {-1, -1, -1, 0, 0, 1, 1, 1};
const int dy[8] = {-1, 0, 1, -1, 1, -1, 0, 1};
struct Node {
int x, y;
bool operator < (const Node &rhs) const {
if (x == rhs.x) return y < rhs.y;
return x < rhs.x;
}
} a[N], b[N], c[N];
int an, bn, cn, row[N], col[N], cnt, w[N], v[N], f[N], dgr[N], ans;
int vis[N], sta[N], top, dfs_clock, dfn[N], low[N], be[N], id;
int head1[N], nxt1[M], pnt1[M], tot1, head2[N], nxt2[M], pnt2[M], tot2;
std::map<Node,int> mp;
std::queue<int> Q;
int read() {
int x = 0; char c = getchar();
while (c < '0' || c > '9') c = getchar();
while (c >= '0' && c <= '9') {
x = (x << 3) + (x << 1) + (c ^ 48);
c = getchar();
}
return x;
}
int min(int x, int y) {
return x < y ? x : y;
}
int max(int x, int y) {
return x > y ? x : y;
}
void add_edge1(int u, int v) {
nxt1[++tot1] = head1[u];
head1[u] = tot1, pnt1[tot1] = v;
}
void add_edge2(int u, int v) {
nxt2[++tot2] = head2[u];
head2[u] = tot2, pnt2[tot2] = v;
}
void build(int rr, int cc) {
for (int i = 1; i <= an; ++i) { //a->a
if (!row[a[i].x]) row[a[i].x] = ++cnt;
++w[row[a[i].x]], mp[a[i]] = row[a[i].x];
}
for (int i = 1; i <= bn; ++i) { //b->b
if (!col[b[i].y]) col[b[i].y] = ++cnt;
++w[col[b[i].y]], mp[b[i]] = col[b[i].y];
}
for (int i = 1; i <= an; ++i) //b->a
if (col[a[i].y]) add_edge1(col[a[i].y], row[a[i].x]);
for (int i = 1; i <= bn; ++i) //a->b
if (row[b[i].x]) add_edge1(row[b[i].x], col[b[i].y]);
for (int i = 1; i <= cn; ++i) { //a->c, b->c, c->abc
if (row[c[i].x]) add_edge1(row[c[i].x], i);
if (col[c[i].y]) add_edge1(col[c[i].y], i);
for (int j = 0; j < 8; ++j) {
int p = c[i].x + dx[j], q = c[i].y + dy[j];
if (p && p <= rr && q && q <= cc && mp.count((Node){p, q}))
add_edge1(i, mp[(Node){p, q}]);
}
}
}
void tarjan(int cur) {
dfn[cur] = low[cur] = ++dfs_clock, sta[++top] = cur, vis[cur] = 1;
for (int i = head1[cur]; i; i = nxt1[i]) {
if (!dfn[pnt1[i]]) tarjan(pnt1[i]), low[cur] = min(low[cur], low[pnt1[i]]);
else if (vis[pnt1[i]]) low[cur] = min(low[cur], dfn[pnt1[i]]);
}
if (dfn[cur] == low[cur]) {
be[cur] = ++id, v[id] = w[cur], vis[cur] = 0;
while (sta[top] != cur) {
int x = sta[top];
be[x] = id, v[id] += w[x], vis[x] = 0, --top;
} --top;
}
}
int main() {
int n = read(), rr = read(), cc = read();
for (int i = 1; i <= n; ++i) {
int x = read(), y = read(), t = read();
if (t == 1) a[++an] = (Node){x, y};
else if (t == 2) b[++bn] = (Node){x, y};
else c[++cn] = (Node){x, y}, w[++cnt] = 1, mp[c[cn]] = cnt;
}
build(rr, cc);
for (int i = 1; i <= cnt; ++i)
if (!dfn[i]) dfs_clock = 0, tarjan(i);
for (int i = 1; i <= cnt; ++i)
for (int j = head1[i]; j; j = nxt1[j])
if (be[i] != be[pnt1[j]]) ++dgr[be[pnt1[j]]], add_edge2(be[i], be[pnt1[j]]);
for (int i = 1; i <= id; ++i) if (!dgr[i]) Q.push(i);
while (!Q.empty()) {
int cur = Q.front(); Q.pop();
f[cur] += v[cur], ans = max(ans, f[cur]);
for (int i = head2[cur]; i; i = nxt2[i]) {
f[pnt2[i]] = max(f[pnt2[i]], f[cur]);
if (--dgr[pnt2[i]] == 0) Q.push(pnt2[i]);
}
}
printf("%d\n", ans);
return 0;
}
时间复杂度 $O()$