求助,能看个题吗

P2272 [ZJOI2007] 最大半连通子图

badFlamesへ @ 2022-07-08 20:29:20

这是52pts的代码,关于那个统计的想法是每发现一个合法的链的长度就把这个长度扔到桶里,最后从桶中取出最大值即可。这个想法错在哪?求大佬们指教

#include <bits/stdc++.h>
#define def register auto
#define LL long long
using namespace std;
const int N = 1e6 + 5;

inline LL read() {
    LL x = 0, w = 0; char ch = getchar();
    while(!isdigit(ch)) { w |= ch == 45; ch = getchar(); }
    while(isdigit(ch)) { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
    return w ? -x : x;
}
#define doge read()

int n, m;
LL sto_txn_orz;
int I_am_not_strong, I;

vector <int> Link[N], Lx[N];

int dfn[N], low[N], Ti;
int st[N], top, col[N], cnt, Lnode[N], Rnode[N], sz[N];
bool vis[N];

void tarjan(int u) {
    dfn[u] = low[u] = ++Ti;
    st[++top] = u; vis[u] = true;
    for(auto v : Link[u]) {
        if(!dfn[v]) {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        }
        else if(vis[v]) low[u] = min(low[u], dfn[v]);
    }
    if(low[u] == dfn[u]) {
        cnt++; def v = 0;
        do {
            v = st[top--]; vis[v] = false;
            col[v] = cnt;
            sz[cnt]++;
        } while(v != u);
    }
}

LL f[N], ans;
int ind[N], outd[N];
LL bucket[N];

inline void sto(LL x) {
    x = (x + sto_txn_orz) % sto_txn_orz;
}

set <int> vx[(int)2e5];

inline void Toposort() {
    queue <int> Q;
    for(def i = 1; i <= cnt; i++) 
        if(!ind[i]) {
            Q.push(i);
            sto(++bucket[sz[i]]);
        }

    while(!Q.empty()) {
        def u = Q.front(); Q.pop();
        f[u] += sz[u];
        for(auto v : Lx[u]) {
            f[v] = max(f[v], f[u]);
            if(!outd[v]) {
                sto(++bucket[f[v] + sz[v]]);
            }
            if(! --ind[v]) Q.push(v);
        }
    }
}

inline void Debug() {
    printf("cnt = %d\n", cnt);
    for(int i = 1; i <= n; i++) {
        printf("col[%d] = %d\n", i, col[i]);
    }

    for(def i = 1; i <= cnt; i++) {
        for(auto v : Lx[i]) {
            printf("%d -> %d\n", i, v);
        }
    }
    for(def i = 1; i <= 10; i++) {
        printf("b[%d] = %d\n", i, bucket[i]);
    }
}

signed main() {
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("Ans.txt", "w", stdout);
#endif
    if(I_am_not_strong) {
        while(true) I %= sto_txn_orz;
    }
    n = doge, m = doge, sto_txn_orz = doge;
    for(def i = 1; i <= m; i++) {
        def u = doge, v = doge;
        Link[u].push_back(v);
        Lnode[i] = u; Rnode[i] = v;
    }

    for(def i = 1; i <= n; i++) if(!dfn[i]) tarjan(i);
    for(def i = 1; i <= m; i++) {
        def x = col[Lnode[i]], y = col[Rnode[i]];
        if(x != y) {
            if(vx[x].find(y) != vx[x].end()) continue;
            vx[x].insert(y);
            Lx[x].push_back(y);
            ind[y]++;
            outd[x]++;
        }
    }

    Toposort();
    for(def i = 1; i <= cnt; i++) {
        if(!outd[i]) ans = max(ans, f[i]);
    }

    //Debug();

    cout << ans << endl << sto(bucket[ans]);
}

by Hoks @ 2023-02-04 19:19:33

@badFlamesへ 重边?


|