求助,想不明白求环内的距离的一些细节
查看原帖
求助,想不明白求环内的距离的一些细节
960410
aru123楼主2023/10/13 19:41

俺的问题在于,简单环虽然不能共边但是可以共点,我看题解的代码基本都是这样的:

inline void solve(int u,int v,int w){
    //参数w为非树边的边权
    ++ext;
    int pw,pre = w,i = v;
    while(i!=fa[u]){
        sum[i] = pre;
        pre += b[i];
        i = fa[i];
    }
    sum[ext] = sum[u]; //把整个环的边权和存到方点上
    sum[u] = 0;//这里
    i = v;
    while(i!=fa[u]){
        pw = min(sum[i],sum[ext]-sum[i]);
        //找最短路,建树边
        adj[ext].push_back(edge(i,pw));
        adj[i].push_back(edge(ext,pw));
        i = fa[i];
    }
}

开了一个数组来记到环起始点的距离,然后记一个环的距离,对起点的值记0。但是几个环共点的话,又不能保证有一样的起点,例如对例图里从9号点开始跑,3是{1,2,3,4}这个环的起点,1是{1,5,6}这个环的起点,求1-3的距离是

min(abs(sum[1] - sum[3]), cir - abs(sum[1] - sum[3])) = 0。

到底是我理解错了呢还是本身这种搞法是不对的?

2023/10/13 19:41
加载中...