Journey

_H17_ · 2026-10-22 19:30:52 · 题解

题目分析

首先考虑每个边都需要打卡一次，所以所有边权都得被计算一次。

考虑打卡之间移动的代价。首先你每次走一段路一定是走了一个欧拉路径，因为折返是不优的（至少一定可以替换成代价不比原来大的火车）。因此对于所有度数为奇数的点，你都需要开始或结束一段路径。显然把环插入进这样的路径可以使得所有偶度点都不作为一个路径的开始或结尾。

因此你只需要把所有奇度点两两配对（显然总度数是偶数，奇度点的数量是偶数），表示 u 作为上一段路径的结尾，然后接下来火车到 v 开始下一段。至于起点这不重要，反正起点在路径之中的话就把这个路径前一半劈开，在最后走回去的时候经过。

在考虑怎么匹配之前，先考虑怎么快速算火车的代价。考虑 u,v，我们尝试枚举编号最大的边（假设编号是 i）。可以以这个代价坐火车的前提是：1\sim i 的边可以使 u,v 连通，并且边 i 在这个连通块中。

因此考虑对这个枚举的过程持久化下来，也就是建一个 Kruskal 重构树。我们按照编号从小到大依次加入每个边，假设加入的边是 (u,v)。如果 u,v 不在一个连通块，那么把两者所在连通块对应的根往一个虚点上连接（这个虚点是新连通块的根），并令这个新点的点权为这个边的边权（点权表示当前连通块内互相走的最小代价）；如果两者在同一个连通块，那就给这个连通块对应的根的权值和边权取较小值即可，因为这个连通块中任意两个点都可以走到这个边这里再回去。接下来把所有点权变成根链上点权的最小值，因为 u\to v 可以先走到 \operatorname{lca}(u,v)，然后往上走到任意一个点再回去。

接下来就是一个简单的贪心匹配，你考虑由于这个树的权值构成小根堆，所以尽量选择 \operatorname{lca}(x,y) 深度更大的 x,y 匹配起来。也就是你考虑递归的考虑每个点。如果叶子是奇度点那就返回 1 表示有一个还没匹配；如果在子节点中有很多节点返回了 1 那就把这里的都两两配对，最后看是否剩下点了来返回 0 或 1。

时间复杂度 O(n\log n+m)，应该可以写带权的并查集然后加上按秩合并，做到 O(n\alpha +m)。

代码

#include<bits/stdc++.h>
using namespace std;
constexpr int N=1e6+1,Inf=0x3f3f3f3f;
int T,n=(N-1),m,fa[N<<1],deg[N],val[N<<1],tot=(N<<1)-1;
long long ans;
vector<array<int,3> >edges;
vector<int>e[N<<1];
void clear(){
    edges.clear();
    for(int i=0;i<=tot;i++){
        e[i].clear();
        val[i]=0,fa[i]=i;
    }
    for(int i=0;i<=n;i++)
        deg[i]=0;
    ans=tot=0;
    return;
}
int findfa(int u){
    return fa[u]==u?u:(fa[u]=findfa(fa[u]));
}
void dfs(int u,int fath){
    val[u]=min(val[u],val[fath]);
    for(auto v:e[u])
        dfs(v,u);
    return;
}
int dp(int u){
    int ret=0;
    for(auto v:e[u])
        ret+=dp(v);
    if(u<=n&&(deg[u]&1))
        ret++;
    ans+=1ll*(ret/2)*val[u];
    return ret&1;
}
void task(){
    clear();
    cin>>n>>m;
    tot=n;
    for(int i=1,u,v,w;i<=m;i++){
        cin>>u>>v>>w;
        deg[u]++,deg[v]++;
        edges.push_back({u,v,w});
        ans+=w;
    }
    for(auto ed:edges){
        int u=ed[0],v=ed[1],w=ed[2];
        u=findfa(u),v=findfa(v);
        if(u!=v){
            fa[u]=fa[v]=(++tot);
            val[tot]=w;
            e[tot].push_back(u),e[tot].push_back(v);
        }
        else
            val[u]=min(val[v],w);
    }
    val[0]=Inf;
    dfs(tot,0),dp(tot);
    cout<<ans<<'\n';
    return;
}
string program(){
    cin.tie(nullptr)->ios::sync_with_stdio(0);
    for(cin>>T;T;T--)
        task();
    return"H17";
}
string H17=program();
signed main(){
    return 0;
}