网络瘤24题练习笔记如何制作？

本文共计7013个文字，预计阅读时间需要29分钟。

前言+看似并不知道要说什么（？）+ 网络流写麻了+ （一）最长+ $k$ + 区间集问题+ 题意：给定+ $n$ + 个左闭右开的区间，从中选择一些区间，使得数轴上没有任意一点被超过+

前言

貌似并不知道要说什么（？）

网络流写麻了

（一）P3358 最长 $k$ 重区间集问题

题意：给定 $n$ 个左闭右开的区间，从这些区间中选取一些区间，使得数轴上没有任何一个点被超过 $k$ 个区间包含，并使得区间覆盖长度最大。

题意没给 $l,r$ 范围，先离散化。

先找流量和费用。首先有一个的隐性条件限制。可以想到将次数作为流量，显然长度就作为花费。

那么怎么表示选择一个区间呢？我们可以将区间左端点连向右端点，流量为 $1$，费用该区间的长度。

一点最多选 $k$ 次，那么我们对于数轴上每一个点 $i$ 连向 $i+1$，容量为 $k$，费用为 $0$。

跑一边最大费用最大流即可。

（二）P4014 分配问题

题意：$n$ 个工件分给 $n$ 个工人，第 $i$ 个人做第 $j$ 个工件的效益为 $c_{i,j}$，求问在一个零件只能匹配一个工人，并且一个工人只能加工一个零件的情况下，效益最大是多少。

显然有一个二分图的模型，把工人放到左边，零件放到右边。中间是若干边。

很套路的，建立一个虚拟源点 $s$，连向每一个工人，容量为 $1$，费用为 $0$，表示一个工人只能匹配一个，没有匹配零件所以没有费用。

同样，建立一个虚拟汇点 $t$，每一个零件连向汇点，容量为 $1$，费用为 $0$。