题解 P3358 【最长k可重区间集问题】
皎月半洒花
2020-03-18 08:31:10
感觉此题大部分题解都一点也不负责任。
本人十分不赞同，对于一道网络流题，一篇题解只说怎么建图不说思路的行为。我就想请问，难道做一道题的目的，就只在于做这一道题吗？A了就好？原理思路什么爱管不管？这能叫题解？
网络流题的重点就是在于建图。如果这都能一笔带过，那还做个锤子？
毫不夸张的说，如果张三做网络流题的时候就这么似是而非，就算他勤勤恳恳地做完了24题，省选的时候也运气好遇到了网络流题，做出来的概率绝对不高，或者说就根本不可能做出来。
你说，网络流题是什么？到现在为止还只是一个靠经验和阅历通杀的题目类别。所以网络流题需要格外重视经验的积累，知其然知其所以然。
总之呢，一道网络流题，不仔细分析思路直接告诉你怎么建图，就是在耍流氓。
_____
> 给定实直线 $ L $ 上 $ n $ 个开区间组成的集合 $ I $，和一个正整数 $ k $，试设计一个算法，从开区间集合 $ I $ 中选取出开区间集合 $ S \subseteq I $，使得在实直线 $ L $ 的任何一点 $ x $，$ S $ 中包含点 $ x $ 的开区间个数不超过 $ k $。且 $ \sum\limits_{z \in S} | z | $ 达到最大。这样的集合 $ S $ 称为开区间集合 $ I $ 的最长 $ k $ 可重区间集。$ \sum\limits_{z \in S} | z | $ 称为最长 $ k $ 可重区间集的长度。
>
> 对于给定的开区间集合 $ I $ 和整数 $ k $，计算开区间集合 $ I $ 的最长 $ k $ 可重区间集的长度。
>
> $ 1 \leq n \leq 500, 1 \leq k \leq 3 $
首先一拿出来，这不就是匹配问题嘛？一个点最多匹配 $k$ 个区间。于是每个位置建一个点，然后连向覆盖自己的点，然后…好像不太对？其一他没给下标的取值范围，其二一个线段覆盖多个点，要么都覆盖要么都不覆盖，这个限制很难表示…
于是好像不知道从何处入手了。发现一个这样的性质，就是永远不会选择 $k$ 个以上交于 $1$ 点的区间。也就是说，如果两个区间彼此之间没有交，就可以同时选；否则能不能同时选，看情况。这像极了「限制」，也就是如果两个区间之间没有交，那两者不存在限制；否则存在 $k$ 的限制。
根据一开始的匹配，可以猜到大致上用网络流是可行的。并且似乎网络流很适合用流量来表征限制。那么考虑，如果两个区间不存在限制，那么应该怎么办——网络流类似电流，所以此时如果串联的话，就代表着可以同时选；那么如果存在限制，就意味着不能串联。根据这一点，考虑如何串联。发现本质上是将两个不交的区间中间连 $f=\infty,c=0$ 的边。
这一点就引申出两个建图方法，其本质是相同的：
1、建立一个超级源 $\rm S$ 和一个源 $\rm S'$ ，中间连 $f=k,c=0$ 的边，目的是提供初始流量。$\rm S'$ 向每个区间的左端点连一条 $f=1,c=-1$ 边。然后区间左端点向右端点连边 $f=1,c=-len$ 表示贡献，每个右端点再向 $\rm T $ 连边即可。如果两个区间不交，就由一个区间的 $r$ 连向另一个区间的 $l$ （当然要按秩啦）。思考这样做的合理性，对于相交的区间，一定是并联；否则的话就是串联（其实叫做混连，但是问题不大）。
2、建立一个源 $\rm S$ 连向数轴上的 $0$ 位置，$f=k,c=0$。然后数轴上每个 $i>0$ 向 $i+1$ 连边 $f=k,c=0$。最后 $maxright$ 向 $\rm T$ 连边。对于一个区间，连法跟1相同。
注意：
1、为什么要拆点？此处拆点的作用值得注意。对于一个区间，本质上应该抽象成一个点。但是在流图里是不存在「点权」这个概念的。所以需要把点权转边权，拆点的作用便在于此。
2、其实上面两个方法，可以通过初中物理里面什么「判断两个电路图是否等价」的知识来解决的233
3、由于本题保证了「开区间」，所以可以直接 $l\to r,len=r-l$ 。当然如果是闭区间，只需要改成 $l\to r+1$ 即可。
4、上面的第二个方案，发现最终可能存在很多数轴上的点 $i$ 只与 $i-1,i+1$ 连了 $f=k,c=0$ 的边，所以是没用的，离散化掉就好了。
```cpp
const int N = 200010 ;
const int I = 998244353 ;
#define ft first
#define sc second
#define to(k) e[k].to
#define fr(k) e[k].from
#define fw(k) e[k].flow
#define ct(k) e[k].cost
#define next(k) e[k].next
#define pint pair<int, int>
struct Edge{
int to ;
int from ;
int flow ;
int cost ;
int next ;
}e[N * 2] ;
int _s ;
int _t ;
int ans ;
int res ;
int cnt ;
int n, m ;
int g[N] ;
int vis[N] ;
int dis[N] ;
int pre[N] ;
int head[N] ;
int _last[N] ;
queue <int> q ;
void add(int u, int v, int f, int c){
to(++ cnt) = v ;
next(cnt) = head[u] ;
fw(cnt) = f ; ct(cnt) = c ;
fr(cnt) = u ; head[u] = cnt ;
}
bool spfa(){
fill(g, g + n + 1, I) ;
fill(dis, dis + n + 1, I) ;
fill(vis, vis + n + 1, 0) ;
q.push(_s) ; vis[_s] = 1 ; dis[_s] = 0 ;
while (!q.empty()){
int x = q.front() ;
q.pop() ; vis[x] = 0 ;
for (int k = head[x] ; ~k ; k = next(k))
if (dis[to(k)] > dis[x] + ct(k) && fw(k)){
dis[to(k)] = dis[x] + ct(k) ;
g[to(k)] = min(fw(k), g[x]) ;
pre[to(k)] = x ; _last[to(k)] = k ;
if (!vis[to(k)]){
q.push(to(k)) ;
vis[to(k)] = 1 ;
}
}
}
return (bool)(dis[_t] < I) ;
}
void ek(){
while (spfa()){
int x = _t ;
res += g[_t] ;
ans += g[_t] * dis[_t] ;
//cout << g[_t] << " " << ans << endl ;
while (x != _s){
fw(_last[x]) -= g[_t] ;
fw(_last[x] ^ 1) += g[_t] ;
x = pre[x] ;
}
}
}
int len[N] ;
pint base[N] ;
int _n, _k, tot ;
map <int, int> Id, buc ;
map <int, int> :: iterator t ;
int main(){
int u, v, f, c ;
cin >> _n >> _k ; cnt = -1 ;
memset(head, -1, sizeof(head)) ;
for (int i = 1 ; i <= _n ; ++ i){
cin >> base[i].ft >> base[i].sc ;
len[i] = base[i].sc - base[i].ft ;
}
for (int i = 1 ; i <= _n ; ++ i){
if (!Id.count(base[i].ft)) buc[base[i].ft] ++ ;
if (!Id.count(base[i].sc)) buc[base[i].sc] ++ ;
}
add(0, 1, _k, 0) ; add(1, 0, 0, 0) ;
for (t = buc.begin() ; t != buc.end() ; ++ t)
Id[t->ft] = ++ tot ; _s = 0 ; _t = tot + 1 ;
for (int i = 1 ; i <= tot ; ++ i)
add(i, i + 1, I, 0), add(i + 1, i, 0, 0) ;
for (int i = 1 ; i <= _n ; ++ i){
//cout << Id[base[i].ft] << " " << Id[base[i].sc] << endl ;
add(Id[base[i].ft], Id[base[i].sc], 1, -len[i]) ;
add(Id[base[i].sc], Id[base[i].ft], 0, len[i]) ;
}
n = _t + 1 ; ek() ;
cout << -ans << endl ;
}
```