「题解」MUL

第一眼看暴力水题，第二眼看筛法水题，第三眼想DP，没想到正解是…最大流……

一 题目

原题链接

描述

有 N 个宝石，编号为 1, 2, .., N
你可以进行任意次以下操作（可以一次也不做）

• 选择一个正整数 x，将所有编号为 x 的倍数的宝石打碎

最后，对于每个没有被打碎的宝石 i，你可以获得 a_i 元。要注意的是，有些 a_i 是负值，这意味着你要倒贴钱。

在最好的情况下，你能获得多少元呢？

输入

第一行一个整数 N，代表共有 N 个宝石
第二行 N 个整数，分别代表 a_1, a_2, …, a_N

输出

一行一个整数，表示你最多可以得到的钱

---

二 题解

初步分析
先不妨称砸掉宝石为筛去一个数值。设筛去的总权值为$v$，获得的利益为$w$，则有$w=\sum\limits_{i=1}^n a_i -v$。显然，$v$越小，$w$越大，得到的答案越优。

也就是说，要让删除的数之和最小。

问题的转化
考虑我们删除一个数的条件。删掉第$k$个数，必须要将编号为$2\times k,3\times k,…,ik(ik\leqslant n)$的数一起删掉。
不妨从编号为$k$的数向编号为$k$的倍数的数$ik$连一条有向边，那么我们会得到一张图。现在再分析删除一个数的条件：即是将从该节点所能到达的所有节点删除。那么这时候就可以引入一个新的概念：闭合子图。

• 闭合子图：在一张图中选出一些节点，它们及从它们所能到达的所有节点组成原图的的一张闭合子图。

同时这张图上每个节点都是有权值的（即问题中宝石的价值），我们要让选出的闭合子图权值最小。那么问题转化成了在我们所建的图中，求出最小权闭合子图。

网络流模型
先抛开最小权闭合子图。

我们知道最大权闭合子图的网络流模型：将图中所有正权节点与源点$s$相连，所连边的流量限制为节点权值；所有负权节点与汇点$t$相连，所连边的流量限制为节点权值的相反数（绝对值）；图上原有边的流量限制为$\infty$。设$s\to t$的最小割（最大流）的大小为$g$，则最大权闭合子图的权值和为$\sum\limits_{1\leqslant i\leqslant n}^{a_i>0}a_i - g$。
说得像人话一点，就是图上所有正权值之和减最小割。

以上结论我并不会证明，但是它是对的。好了，剩下的问题是用这个模型求出“最小权闭合子图”。

不妨将节点权值全部乘上$-1$，套用上面的模板，那么我们求出来的最大权闭合子图即是最小权闭合子图大小的相反数。设最小权闭合子图大小为$s$，则有$s = -(-\sum\limits_{1\leqslant i\leqslant n}^{a_i<0}a_i - g)$，即图上所有负权值的绝对值之和减最小割。

设最优解为$f$，则有$f = \sum\limits_{i=1}^na_i - s = \sum\limits_{i=1}^na_i +(-\sum\limits_{1\leqslant i\leqslant n}^{a_i<0}a_i - g)$。好了，问题解决了。

用Dinic求出这个$g$，注意，long long不要忘开，边数开多一点，然后千万别写当前弧优化！

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<queue>
using namespace std;

#define LL long long

const int CP=110;
const int CE=CP*CP*20;

const LL INF=0x3f3f3f3f3f3f3f3f;

LL read(){
    LL s=0,ne=1; char c=getchar();
    for(;c<'0'||c>'9';c=getchar()) if(c=='-') ne=-1;
    for(;c>='0'&&c<='9';c=getchar()) s=(s<<1)+(s<<3)+c-'0';
    return s*ne;
}

class fs{
  public:
      int from,to,nxt; LL cap,flow;
      void init(int f,int t,int n,LL c,LL fl)
      {from=f;to=t;nxt=n;cap=c;flow=fl;}
}E[CE];
int hd[CP],ecnt=1;
void add(int x,int y,LL z){
    E[++ecnt].init(x,y,hd[x],z,0);
    hd[x] = ecnt;
    E[++ecnt].init(y,x,hd[y],0,0);
    hd[y] = ecnt;
}

//v define
int n;
LL a[CP];
void copy(int *a,int *b,int pos,int sz){
    for(int i=pos;i<pos+sz;i++) b[i] = a[i];
}

//dinic
int dep[CP];
bool build(int s,int t){ //构造分层图 
    memset(dep,0,sizeof(dep));
    dep[s] = 1;
    
    queue<int> Q;
    Q.push(s);
    
    while(!Q.empty()){
        int u = Q.front();
        Q.pop(); 
        
        for(int k=hd[u]; k; k=E[k].nxt){
            int v = E[k].to;
            if(!dep[v] && E[k].cap-E[k].flow>0){
                dep[v] = dep[u]+1;
                Q.push(v);
            }
        }
    }
    
    return dep[t];
}
LL augment(int u,int t,LL rst){ //多路增广 
    if(u == t) return rst;
    
    LL used = 0;
    for(int k=hd[u]; k; k=E[k].nxt){
        fs &e = E[k];
        
        if(dep[e.to] == dep[u]+1){
            LL a = augment(e.to,t, min(rst-used,e.cap-e.flow));
            if(a){
                used += a;
                E[k].flow += a;
                E[k^1].flow -= a;
                if(used == rst) return rst;
            }
        }
    }
    
    return used;
}
LL mf(int s,int t){ //最大流
    LL _mf = 0;
    while(build(s,t))
        _mf += augment(s,t,INF);
    return _mf;
}

int main()
{
    n = read();
    for(int i=1;i<=n;i++)
        a[i] = read();
        
    for(int i=1;i<=n;i++)
        for(int k=2;i*k<=n;k++)
            add(i,i*k,INF); //原图内的边
    int s = n+1,t = n+2;
    for(int i=1;i<=n;i++)
        if(a[i] > 0) add(i,t,a[i]); //反着连边，搞不懂自己推一推
            else add(s,i,-a[i]);
    
    LL sum = 0,sigma = 0;
    for(int i=1;i<=n;i++) //求负权的绝对值之和 
        if(a[i] < 0) sigma -= a[i];
    for(int i=1;i<=n;i++)
        sum += a[i];
    
    printf("%lld",sum+(sigma-mf(s,t)));    
            
    return 0;
}