社区讨论
求助,想不明白求环内的距离的一些细节
P5236【模板】静态仙人掌参与者 1已保存回复 1
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 1 条
- 当前快照
- 1 份
- 快照标识符
- @lo13gr7e
- 此快照首次捕获于
- 2023/10/22 14:35 2 年前
- 此快照最后确认于
- 2023/11/02 14:05 2 年前
俺的问题在于,简单环虽然不能共边但是可以共点,我看题解的代码基本都是这样的:
CPPinline 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 条回复,欢迎继续交流。
正在加载回复...