【题解】[TJOI2010]电影迷

wgyhm · 2021-02-03 15:57:20 · 题解

[TJOI2010]电影迷

题目大意：

选择 i 获得 v_i 的价值，选择 i 但是不选择 j 失去 d_{i,j} 的价值（不可逆）。求 \max(\text{最大价值},0)。

〇、前言

这里介绍两种方法。同时请确保你会最大流的基础算法和一定的最小割基础。

一、ex最大权闭合子图

建图

• \begin{cases}(s,x,v_x)&v_x>0\\(x,t,-v_x)&v_x<0\end{cases}

答案 = 正权点之和 - 最小割

含义

因为建图类似于最大闭合权子图，所以含义也可以类比得出。

• 割掉 s 与 x 的边，表示不选择正权点 x；割掉 x 与 t 的边，表示选择负权点 x。

• 如果 s 与 i 有边，表示选择正权点 x；如果 x 与 t 有边，表示不选择负权点 x。

• 割掉 (x,y)，表示选择 x 但是不选择 y，付出 d_{x,y} 的代价。

图示

合法性

如果 s 与 t 连通，则存在正权点 i 和负权点 j 使得 s 到 i 有边，i 到 j 连通，j 到 t 有边，所以 j 一定是 i 的后继。根据含义，选择 i ，不选择 j 却不付出 d_{i,j} 的代价，是不合法的。

图示：

如果 s 与 t 不连通。

1. 割断（选择）了负权点 j 与 t 的边 (j,t)，也就是选择了 j 的前驱正权点 i 和 j 。根据最小割的定义，j 的前驱 i 不会被割，同时也不选择中间的边 (i,j) 。
2. 割断了 (i,j) ，也就是选择了正权点 i ，不选择负权点 j ，恰好减去了所谓的体验值。
3. 割断了 (s,i)，也就是选择了负权点 j ，放弃了正权点 i，同时也没有减去体验值。

图示：

最优性

最小割 = 不选择的正权点之和 + 选择的负权点之和的绝对值 + 减少的 d。

答案 = 选择的正权点之和 + 选择的负权点之和 - 减少的 d 。

最小割保证了答案最大。

代码看别的博客吧。

二、集合划分模型

众所周知，最小割不可以跑负权边。

由于有负数，根据数据范围把所有的分数 v_x 都加上一个大正整数 base 使得所有 v_x 都变为正数。

设 v'_x=v_x+base

建图

• (s,i,v'_i),(i,t,base)
• (i,j,d_{i,j})

答案 = \sum\limits_{i=1}^n v_i+base\times n-最小割

含义

• 割断 (s,i) 表示 i 不选择，割断 (i，t) 表示选择 i。

正确性

原来没有加上 base 的正权网络是正确的，加上以后为什么还是对的呢？

根据含义，总共会割 n 条与 s 或者 t 相接的边。所以总共额外增加的 base\times n。而所有情况都有额外加上了 base\times n ，相对的大小就不变了。

Code：

//Dinic...

const int eps=2e3;
signed main(){
    rg int i,x,y,z,sum=0;
    read(n);read(m);s=0;t=n+1;
    for (i=1;i<=n;i++) read(x),Dinic::ins(s,i,x+eps),Dinic::ins(i,t,eps),sum+=x;
    while (m--) read(x),read(y),read(z),Dinic::ins(x,y,z);
    sum=sum+eps*n-Dinic::Dinic();
    printf("%lld",sum);
    return 0;
}