【网络流】线性规划的最小割建模方式 – Houjikan

前几天在师大附中听课,大概了解了一些关于网络流的建模方式,然后今天上午做了一些题目,在这里总结一下。

最小割的线性规划建模方式:

  有一些0/1变量Xi怎么怎么样之后会消耗某些代价或者获得某些利益,而最后的总收益可以写成如下的形式:

          min{ Σmax{Xi-Xj,0}*Wi }

    其中Wi必须是正数。

     那么假设源为1,汇为0,就将Xi连一条流量为Wi的边到Xj。

    如果有形如1-Xi之类的形式就是从源向Xi连边,Xi-0这种形式就是Xi向汇点连边。

  那么如果Wi是负数怎么办?

       比如Xi*Wi(Wi<0)

          Xi*Wi=(-Xi)*(-Wi)=(1-Xi)*(-Wi)+Wi

  这样就化成正数了,然后后面的Wi是一个常数,可以全部提到外面去。

  比如我随便YY一个题目。。一堆棋子,其中把第I个变成白色有Wi的不和谐度,变成黑色有Bi的不和谐度,如果某个i和j颜色不一样就会有Ai,j的不和谐度,要求不和谐度最小。。

  恩。。假设1是黑色,0是白色,那么线性规划出来就是

   min{Σmax{Xi,0}*Bi+Σmax{1-Xi,0}*Wi+Σmax{Xi-Xj,0}*Ai,j+Σmax{Xj-Xi,0}*Ai,j}

  那么怎么连边就显而易见了啊。。按照上面的规则连就是了,1代表源,0代表汇。

呀好丑TAT

  有时候会出现让你最大化收益的情况,其实是一样的,因为max{Ai}=-min{-Ai}

  你在里面加个负号就行了,然后化一化就好。

  如果有依赖怎么办?比如说要先选i才能选j

  那么就加上 max{Xj-Xi,0}*INF就行。如果j是1,i是0的话就会有INF的代价。好口怕QAQ。

  比如说最大闭权子图就可以这么做,按照公式推出来建边就行了,显然是正确的OwO。比如选第i件物品的代价是Wi(可正可负)

  Ans=max{min{ΣXi*Wi}+Σmax{Xj-Xi,0}*INF}=-min{-Σ{Xi*Wi}-Σmax{Xj-Xi,0}*INF}

  然后将Wi分正负进行处理,后面第二部分的那个减号就把Xj-Xi改成Xi-Xj就行了。

  线性规划建模很无脑的。。只要初中数学及格就能建了。

  总之网络流也就是建模要想一下(这不废话么摔(╯‵□′)╯︵┻━┻),跑最大流的话……随便吧,反正我是更喜欢ISAP。

 

本文链接:【网络流】线性规划的最小割建模方式,转载请注明。



You must enable javascript to see captcha here!

Copyright © All Rights Reserved · Green Hope Theme by Sivan & schiy · Proudly powered by WordPress

无觅相关文章插件,快速提升流量