求助,马峰良好,RE 版本代码如下,感谢您愿意帮我调试!
#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <stack>
using namespace std;
#define fr first
#define sc second
#define PII pair<int,int>
#define mkp make_pair
const int N = 1e6 + 5,M=5e5;
int dir[8][2]={{0,1},{0,-1},{1,0},{-1,0},{1,1},{-1,-1},{1,-1},{-1,1}};
int n, r, c, x, y, t, ru[N],w[N];
vector<int> e[N],Edge[M];
int dfn[M], low[M], dfncnt, scc[M], sc, sz[M];
stack<int> s;
void add(int x, int y) { e[x].push_back(y); }
void tarjan(int u) {
dfn[u] = low[u] = ++dfncnt;
s.push(u);
for (auto v : e[u]) {
if (!dfn[v]) {
tarjan(v);
low[u] = min(low[u], low[v]);
} else if (!scc[v])
low[u] = min(low[u], dfn[v]);
}
if (low[u] == dfn[u]) {
scc[u] = ++sc;
sz[sc] = w[u];
while (s.top()!=u) {
scc[s.top()] = sc;
sz[sc]+=w[s.top()];
s.pop();
}
s.pop();
}
}
vector<PII> bian;
vector<int> id;
map<PII,int> point;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> r >> c;
/*
1~r 行
r+1~r+c 列
r+c+1~r+c+n 点
*/
for (int i = 1; i <= n; i++) {
cin >> x >> y >> t;
w[r+c+i]=1;
add(x,r+c+i);
add(y+r,r+c+i);
if(t==1) add(r+c+i,x);
else if(t==2) add(r+c+i,y+r);
else bian.push_back(mkp(x,y)),id.push_back(i);
point[mkp(x,y)]=i;
}
int tot=0;
for(auto a:bian){
int i=id[tot++];
for(int j=0;j<8;j++){
int tx=a.fr+dir[j][0],ty=a.sc+dir[j][1];
if(point.count(mkp(tx,ty))) add(r+c+i,point[mkp(tx,ty)]+r+c);
}
}
for (int i = 1; i <= r+c+n; i++)
if (!dfn[i])
tarjan(i);
for (int i = 1; i <= r+c+n; i++) {
for (auto v : e[i]) {
if (scc[i] != scc[v])
Edge[scc[i]].push_back(scc[v]), ru[scc[v]]++;
}
}
vector<int> f(sc + 1, 0);
queue<int> q;
// cout<<"Tarjan\n";
for (int i = 1; i <= sc; i++)
if (!ru[i])
q.push(i), f[i] = sz[i];
while (q.size()) {
int u = q.front();
q.pop();
for (auto v : Edge[u]) {
f[v] = max(f[v], f[u] + sz[v]);
if (!--ru[v])
q.push(v);
}
}
int ans = 0;
for (int i = 1; i <= sc; i++) ans = max(ans, f[i]); //,cout<<i<<' '<<f[i]<<'\n';
cout << ans;
return 0;
}