题解：P12626 [NAC 2025] Most Scenic Cycle

· · 题解

原题的图的条件是：

第二个条件说明如果取对偶图，对偶图的每个点是一个简单环，那么对偶图是一棵树。

然后不难发现图是广义串并联图（可以每次缩掉对偶图的一个叶子）。要求权值最大环，改一下 compress 和 twist 就好了。

#define maxn 1000005
#define inf 0x3f3f3f3f3f3f3f3f

int n,m,res;

struct node{
    int x;
    node(int xx=-inf){x=xx;}
};
node T(node a,node b){
    res=max(res,a.x+b.x);
    return node(max(a.x,b.x));
}
node C(node a,node b){
    return node(a.x+b.x);
}

map<int,node>G[maxn];
int ord[maxn];
void add(int u,int v,node w){
    if(G[u].count(v)) G[u][v]=G[v][u]=T(G[u][v],w);
    else G[u][v]=G[v][u]=w;
}
void dele(int u,int v){
    G[u].erase(v),G[v].erase(u);
}

void build()
{
    queue<int>q; int idx=0;
    For(i,1,n)if(G[i].size()<=2)q.push(i);
    while(q.size()){
        int u=q.front();q.pop();
        if(ord[u])continue;
        ord[u]=++idx;
        if(G[u].size()==1){
            auto [v,w]=*G[u].begin();
            if(G[v].size()<=2)q.push(v);
        }
        if(G[u].size()==2){
            auto [x,w1]=*G[u].begin();
            auto [y,w2]=*G[u].rbegin();
            dele(u,x),dele(u,y);
            add(x,y,C(w1,w2));
            if(G[x].size()<=2)q.push(x);
            if(G[y].size()<=2)q.push(y);
        }
    }
    assert(idx==n);
}

signed main()
{
    n=read(),m=read();
    res=-inf;
    For(i,1,m){
        int u=read(),v=read(),w=read();
        add(u,v,w);
    }
    build();
    cout<<res;
    return 0;
}
/*
6 5
1 2 9
2 3 9
3 4 9
3 4 -9
4 1 9
*/