社区讨论

求助,想不明白求环内的距离的一些细节

P5236【模板】静态仙人掌参与者 1已保存回复 1

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
1 条
当前快照
1 份
快照标识符
@lo13gr7e
此快照首次捕获于
2023/10/22 14:35
2 年前
此快照最后确认于
2023/11/02 14:05
2 年前
查看原帖
俺的问题在于,简单环虽然不能共边但是可以共点,我看题解的代码基本都是这样的:
CPP
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。
到底是我理解错了呢还是本身这种搞法是不对的?

回复

1 条回复,欢迎继续交流。

正在加载回复...