俺的问题在于,简单环虽然不能共边但是可以共点,我看题解的代码基本都是这样的:
inline void solve(int u,int v,int 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。
到底是我理解错了呢还是本身这种搞法是不对的?