orz,求个hack的样例
查看原帖
orz,求个hack的样例
960410
aru123楼主2023/7/7 15:37

我把环的两条相邻的边拆开了之后做dfs,考虑到找到环后是直接退出,需要在Dp的时候把vis标记打上,但是为啥这样做是错的?

#include <iostream>
#include <bits/stdc++.h>
#define ll long long
using namespace std;
template <typename T>
inline void read(T& x){
    x = 0; bool f = 0; char c = getchar();
    while(c < '0' || c > '9'){f = c == '-'; c = getchar();}
    while(c >= '0' && c <= '9'){x = (x << 3) + (x << 1) + (c ^ 48); c = getchar();}
    if(f) x = -x;
}

const int maxN = 1E6 + 5;
int head[maxN], cnt = 0, w[maxN], n, r, e1, e2;
bool vis[maxN], hasCircle;

struct edge{
    int to, next;
    edge(int to = 0, int next = -1):to(to), next(next){}
}edges[maxN << 1];

inline void add(int u, int v){
    edges[cnt] = edge(v, head[u]);
    head[u] = cnt++;
}

struct node{
    ll single, tot;
    node(ll single, ll tot):single(single), tot(tot){}
};

inline void findCircle(int now, int pre){
    vis[now] = 1;
    for(int e = head[now]; ~e; e = edges[e].next){
        int& to = edges[e].to;
        if(e == (pre ^ 1)) continue;
        if(vis[to]){
            r = now;
            e1 = e ^ 1;
            hasCircle = 1;
            return ;
        }
        findCircle(to, e);
        if(hasCircle){
            if(e2 == -1) e2 = e;
            return ;
        }
    }
}

inline node dfs(int now, int pre, int r){
    vis[now] = 1;
    ll fir = 0, sec = 0, tot = 0;
    for(int e = head[now]; ~e; e = edges[e].next){
        int& to = edges[e].to;
        if(e == (pre ^ 1) || to == r) continue;
        auto it = dfs(to, e, r);
        tot = max(tot, it.tot);
        ll nS = it.single + w[e >> 1];
        if(nS >= fir) swap(fir, sec), fir = nS;
        else if(nS > sec) sec = nS;
    }
    return node(fir, max(fir + sec, tot));
}

inline void getAns(){
    ll res = 0;
    for(int i = 1; i <= n; i++){
        hasCircle = 0;
        e1 = e2 = -1;
        if(!vis[i]){
            findCircle(i, -1);
            if(hasCircle) res += max(dfs(r, e1, r).tot, dfs(r, e2, r).tot);
            else res += dfs(i, -1, -1).tot;
        }
    }
    printf("%lld", res);
}

int main(){
    int to;
    read(n);
    memset(head, -1, sizeof(head));
    memset(vis, 0, sizeof(vis));
    for(int i = 1; i <= n; i++){
        read(to), read(w[i - 1]);
        add(to, i);
        add(i, to);
    }
    getAns();
    return 0;
}
2023/7/7 15:37
加载中...