左右为难,开小RE,开大MLE
查看原帖
左右为难,开小RE,开大MLE
590609
jiangjiangQwQ楼主2024/8/19 22:17

求助,马峰良好,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;
}
2024/8/19 22:17
加载中...