? 解题记录 ? ? 强连通分量 ? ? 洛谷 ?    2018-11-13 10:01:47    472    0    0

## 题目描述

1. “横天门”：由该门可以传送到同行的任一宫室；

2. “纵寰门”：由该门可以传送到同列的任一宫室；

3. “自由门”：由该门可以传送到以该门所在宫室为中心周围8格中任一宫室（如果目标宫室存在的话）。

## 输入输出样例

```10 7 7
2 2 1
2 4 2
1 7 2
2 7 3
4 2 2
4 4 1
6 7 3
7 7 1
7 5 2
5 2 1```

`9`

## 最后一样的缩点，按拓扑序找带权最长链。

```// luogu-judger-enable-o2
#include<cstdio>
#include<map>
#include<cstring>
#include<algorithm>
#include<stack>
using namespace std;
const int maxn = 1.5e6 + 5;
const int maxm = 1e5 + 5;
typedef pair<int, int > pii;
int dx[] = {0, 0, 1, -1, 1, -1, 1, -1};
int dy[] = {1, -1, 0, 0, 1, 1, -1, -1};
map<pii, int > id;
map<int, int > Rn, Cn;
int n, R[maxm], C[maxm], x[maxm], y[maxm], t[maxm];

struct edge {
int v, next;
} e[maxn << 1];
int head[maxn], cnt, ncnt, dcnt, bcnt;
void adde(const int &u, const int &v) {
}

namespace NG {
struct edge {
int v, next;
} e[maxn << 1];
void adde(const int &u, const int &v) {
}
int dp[maxn];
void init() {
memset(dp, -1, sizeof(dp));
}
int DP(int u) {
if(~dp[u]) return dp[u];
dp[u] = 0;
for(register int i = head[u]; i; i = e[i].next) {
int v = e[i].v;
DP(v), dp[u] = max(dp[u], dp[v]);
}
return (dp[u] += w[u]);
}
int work() {
NG::init();
int ans = 0;
for(register int i = 1; i <= bcnt; ++i)
ans = max(DP(i), ans);
return ans;
}
}

stack<int > stk;
int dfn[maxn], low[maxn], blk[maxn];
int tarjan(int u) {
stk.push(u);
dfn[u] = low[u] = ++dcnt;
for(register int i = head[u]; i; i = e[i].next) {
int v = e[i].v;
if(blk[v]) continue;
if(dfn[v]) low[u] = min(low[u], low[v]);
else low[u] = min(low[u], tarjan(v));
}
if(dfn[u] == low[u]) {
int v = stk.top();
++bcnt;
while(1) {
blk[v] = bcnt, stk.pop();
NG::w[bcnt] += (v <= n);
if(v == u) break;
v = stk.top();
}
}
return low[u];
}

int main() {
scanf("%d%d%d", &n, &R, &C), ncnt = n;
for(register int i = 1; i <= n; ++i) {
scanf("%d%d%d", &x[i], &y[i], &t[i]);
R[i] = Rn[x[i]], C[i] = Cn[y[i]];
id[make_pair(x[i], y[i])] = i;
if(!R[i]) R[i] = Rn[x[i]] = ++ncnt;
if(!C[i]) C[i] = Cn[y[i]] = ++ncnt;
}
for(register int i = 1; i <= n; ++i) {
if(t[i] == 3) {
int nx, ny, tmp;
for(register int j = 0; j < 8; ++j) {
nx = x[i] + dx[j];
ny = y[i] + dy[j];
if(tmp = id[make_pair(nx, ny)])
}
}
}
for(register int i = 1; i <= ncnt; ++i)
if(!blk[i]) tarjan(i);
for(register int i = 1; i <= ncnt; ++i) {
for(register int j = head[i]; j; j = e[j].next) {
int v = e[j].v;
if(blk[v] != blk[i])
}
}
printf("%d", NG::work());
return 0;
}```

472 人读过

0 条评论