本文共 782 字，大约阅读时间需要 2 分钟。
扩展最大权闭合图
容易想到源点向正点权连边,负点权向汇点连边,流量为各自权值的绝对值
这样初始价值就是正点权的价值
对于限制 ( x , y , v a l ) (x,y,val) (x,y,val),由 x x x向 y y y连边,流量为 v a l val val.
至于正确性,这里有
其实我对这种做法仍然存有疑虑,所幸有第二种做法。
集合划分模型
我们把每个点的点权都加上一个很大的数 b a s e base base
s s s向点 u u u连流量为 v a l u + b a s e val_u+base valu+base的边, u u u向 t t t连流量为 b a s e base base的边
划分到 s s s表示选,划分到 t t t表示不选。
不管划分到哪个集合都多付出了 b a s e base base的花费,相对大小不变,所以不影响选择
对于限制 ( x , y , v a l ) (x,y,val) (x,y,val)连边 ( x , y , v a l ) (x,y,val) (x,y,val)
设想如果存在 s − u − v − t s-u-v-t s−u−v−t的边
要么割掉 s − u s-u s−u保留 u − t u-t u−t,此时 u , v u,v u,v都不选
要么割掉 v − t v-t v−t保留 s − v s-v s−v,此时 u , v u,v u,v都选
要么割掉 u − v u-v u−v,此时 u u u选 v v v不选,且付出了相应的花费
最后的答案就是, ∑ 正 点 权 − 最 小 割 + b a s e ∗ n \sum正点权-最小割+base*n ∑正点权−最小割+base∗n
因为每个点划分集合的时候都多付出了 b a s e base base的花费
转载地址：https://issue-is-vegetable.blog.csdn.net/article/details/115449283 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！
发表评论
最新留言
关于作者
