• 网络流24题总结


    ·搭配飞行员

    题意

      一群正驾驶,一群副驾驶。一些正驾驶可以和副驾驶一起飞。问最多多少架飞机可以飞。

    题解

      二分图最大匹配模型。

      超级源向所有正驾驶连容量为1的边,所有副驾驶向超级汇连容量为1的边。可以一起飞的正副驾驶之间连容量为1的边。跑最大流就是二分图最大匹配。

    ·太空飞行计划

    题意

      m个实验,n个仪器。每个实验需要若干个仪器。激活每个仪器需要一个cost,每个实验有个价值。问激活哪些仪器收益最大。

    题解

      最大权闭合子图问题。可以转化为最小割问题。

      超级源向所有实验连容量为收益边,仪器向超级汇连容量为cost的边。

      如果实验i需要仪器j,则i向j连容量为INF的边。

      则最大收益为收益和-最大流。

      对应的解就是最小割划分出的S集合中的点,也就是最后一次增广找到阻塞流时能从S访问到的顶点。

      定义一个割划分出的S集合为一个解,那么割集的容量之和就是(未被选的A集合中的顶点的权值 + 被选的B集合中的顶点的权值),记为Cut。A集合中所有顶点的权值之和记为Total,那么Total - Cut就是(被选的A集合中的顶点的权值 - 被选的B集合中的顶点的权值),即为我们的目标函数,记为A。要想最大化目标函数A,就要尽可能使Cut小,Total是固定值,所以目标函数A取得最大值的时候,Cut最小,即为最小割。

    ·最小路径覆盖

    题意

      图中的每个点都恰好在路径集合P中的一条路上,称集合P为一个路径覆盖。路径条数最少的覆盖称为最小路径覆盖。给出有向无环图G,求最小路径覆盖。

    题解

      拆点。讲i点拆为Xi和Yi。若i到j之间有边,则Xi向Yj连边。跑二分图最大匹配即可。

      最小路径覆盖的条数=原图顶点数-二分图最大匹配数。

      对于一个路径覆盖,有如下性质:

      1、每个顶点属于且只属于一个路径。
      2、路径上除终点外,从每个顶点出发只有一条边指向路径上的另一顶点。

      所以我们可以把每个顶点理解成两个顶点,一个是出发,一个是目标,建立二分图模型。该二分图的任何一个匹配方案,都对应了一个路径覆盖方案。如果匹配数为0,那么显然路径数=顶点数。每增加一条匹配边,那么路径覆盖数就减少一个,所以路径数=顶点数 - 匹配数。要想使路径数最少,则应最大化匹配数,所以要求二分图的最大匹配。

    ·魔术球

    题意

      N根柱子,依次放编号为1,2,3..的球。要求每次只能在柱顶放球。要求相邻球编号和为完全平方数。

      计算N根柱子最多放多少个球。

     

    题解

      设最多放X个球。那么建立节点1..X,若i<j且i+j为完全平方数,则建一条有向边。那么最小路径覆盖就是最少需要的柱子数。

      顺序枚举A的值,当最小路径覆盖数刚好大于N时终止,A-1就是最优解。

      若二分答案,则每次要重新建图,复杂度更高。

    ·圆桌聚餐

    题意

      n个单位,每个单位ri个人。共m张桌子,每个桌子可容纳ci个人。同桌的人不能同单位。

    题解

      二分图多重匹配。

      超级源向所有单位连容量为单位人数的边,所有桌子向超级汇连容量为桌子容量的边。

      所有单位向所有桌子连边。

      跑最大流,若最大流=总人数,则有解,否则无解。

    ·

  • 相关阅读:
    vue-面试
    使用webpack4搭建一个基于Vue的组件库
    vue 仿今日头条
    如何正确的在项目中接入微信JS-SDK
    vuejs实现折叠面板展开收缩动画
    Vue的watch和computed属性
    Android Studio(十):添加assets目录
    Android Studio(九):引用jar及so文件
    Android Studio(八):Android Studio设置教程
    Android Studio(七):项目从Eclipse到Android Studio迁移
  • 原文地址:https://www.cnblogs.com/aseer/p/8981157.html
一二三 - 开发者的网上家园