关于【网络流】 - 【最小割】建图的询问
  • 板块学术版
  • 楼主brealid
  • 当前回复18
  • 已保存回复18
  • 发布时间2021/2/3 13:28
  • 上次更新2023/11/5 03:51:38
查看原帖
关于【网络流】 - 【最小割】建图的询问
63720
brealid楼主2021/2/3 13:28

【网络流】 - 【最小割】建图常见套路中:

  1. 如果同时选两个节点会有收益(a && b == true),那一般情况会建立一个新点,新点到【源 / 汇】连接流量为收益的边,到可选的两个节点连容量为 Inf 的边
  2. 如果两个节点有么都选,要么都不选有收益(a == b),那一般情况下直接连边,容量为所获得的收益

那下面两种方式,如何连边?

  1. 如果两个节点只要选了一个就有收益(a || b == true)
  2. 如果两个节点选的不一样有收益(a != b)
2021/2/3 13:28
加载中...