题解【CF863F Almost Permutation】

传送门。

$\texttt{Description}$

$n$ 个数，每个数都在 $1$ 至 $n$ 间。$m$ 个形如 $[l,r]$ 中的数不小于或不大于 $v$ 的限制。设 $cnt(i)$ 表示 $i$ 的出现次数，求 $\sum cnt_i^2$ 的最小值。

$1\le n\le 50$，$1\le m\le 100$。

$\texttt{Solution}$

发现数据范围这么小，那么我们可以暴力预处理出，序列中每一个 $a_i$ 可能取到的范围，设为 $[down_i,up_i]$。

然后考虑一个二分图模型。

左边是 $1$ 至 $n$，代表每一个位置，右边是 $1$ 至 $n$，代表序列中每一个位置上可能的值。

每一个位置上只能有一个数，所以我们连 $s\to i$，容量为 $0$，费用为 $1$。

然后对于每一个位置连向它能取到的区间即 $[down_i,up_i]$，流量为 $1$，费用为 $0$。

这些都是非常显然的。

但问题在于，如果我们右边的每一个数，向 $t$ 连一条容量为 $\infty$ 费用为 $1$ 的边（表示一个数可能被多个位置匹配，然后每一个位置都要有 $1$ 的贡献），最终需要求得是 $\sum cnt_i^2$，无法解决。

考虑右边一个数，最多被匹配的上限是 $n$，那么将这个点向 $t$ 连 $n$ 条边，第 $i$ 条边，容量为 $1$，费用为 $i^2-(i-1)^2$。

这是什么意思呢？

考虑它的匹配，容量都一样，那么我们 $\texttt{spfa}$ 在找增光路的时候肯定会找费用最小的几条。

当从第 $i$ 小的边，加入了第 $i+1$ 小的边时，$i^2$ 的那一项恰好被削掉，$(i-1)^2$ 的那一项又被前面的消掉，所以求和起来就是 $(i+1)^2$。

个人感觉像是构造的思想，十分巧妙。也许是一种 $\texttt{trick}$ 但我并不知道。

代码：

int main()
{
    n=read(),m=read();
    s=0,t=n<<1|1;
    for(register int i=1;i<=n;i++) down[i]=1,up[i]=n;
    for(register int i=1;i<=m;i++)
    {
        int opt=read(),l=read(),r=read(),v=read();
        if(opt==1) for(register int j=l;j<=r;j++) down[j]=Max(down[j],v);
        else for(register int j=l;j<=r;j++) up[j]=Min(up[j],v);
    } 
    for(register int i=1;i<=n;i++) if(down[i]>up[i])
    {
        puts("-1");
        return 0;
    }
    for(register int i=1;i<=n;i++)
        for(register int j=down[i];j<=up[i];j++)
            add_edge(i,j+n,1,0);
    for(register int i=1;i<=n;i++) add_edge(s,i,1,0);
    for(register int i=1;i<=n;i++)
        for(register int j=1;j<=n;j++)
            add_edge(i+n,t,1,(j<<1)-1);
    MCMF();
    return 0;
}

注意数组不要开小了。

$$\texttt{The End.by UF}$$