【AtCoder Regular Contest 085 E】MUL | Mrsrz's blog

最小割。

题目大意：

给定 $a_1,a_2,a_3,\ldots,a_n$，你可以执行以下操作：

• 选择一个正整数 $x$，将编号为 $x$ 的倍数的数删去。

要求出剩下的数的和最大是多少。

题解：

如果所有数都是正数，那么有一个最小割模型：

从源点连向 $n$ 个点容量 $0$ 的边，表示选择删除的 $x$。

从 $n$ 个代表原数的点向汇点连容量为 $a_i$ 的边。

从代表删除倍数的点连向它能删除的所有代表原数的点链容量 $+\infty$ 的边。

然后最小割就是最少要从总量中删去的值。

这个图在 $a_i$ 为正时显然是 $0$，但是在 $a_i$ 出现负数的时候，就没法直接做了。

不过我们可以发现，任意一个合法的最小割，都要割掉恰好 $n$ 条边。

所以我们给每条边都赋一个附加权值，让它们变为非负，最后再减掉即可。

Code：

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
#define int long long
const int N=1919810;
struct edge{
    int to,nxt,cap;
}e[N];
int head[233],cnt=1,T,n,iter[233],dep[N],ans;
inline void addedge(int u,int v,int w){
    e[++cnt]=(edge){v,head[u],w},head[u]=cnt;
    e[++cnt]=(edge){u,head[v],0},head[v]=cnt;
}
queue<int>q;
void bfs(){
    dep[0]=1;
    for(q.push(0);!q.empty();){
        int u=q.front();q.pop();
        for(int i=head[u];i;i=e[i].nxt)
            if(e[i].cap&&!dep[e[i].to]){
                dep[e[i].to]=dep[u]+1;
                q.push(e[i].to);
            }
    }
}
int dfs(int u,int f){
    if(!f||u==T)return f;
    for(int&i=iter[u];i;i=e[i].nxt)
        if(e[i].cap&&dep[e[i].to]>dep[u]){
            int d=dfs(e[i].to,min(f,e[i].cap));
            if(d){
                e[i].cap-=d,e[i^1].cap+=d;
                return d;
            }
        }
    return 0;
}
int dinic(){
    for(int flow=0;;){
        memset(dep,0,sizeof dep);
        bfs();
        if(!dep[T])return flow;
        memcpy(iter,head,sizeof head);
        while(int f=dfs(0,1145141919810))flow+=f;
    }
}
main(){
    scanf("%lld",&n);
    T=2*n+1;
    for(int i=1,x;i<=n;++i)
        scanf("%lld",&x),ans+=x,addedge(i,T,x+1e9);
    for(int i=1;i<=n;++i){
        addedge(0,i+n,1e9);
        for(int j=i;j<=n;j+=i)
            addedge(i+n,j,1145141919810);
    }
    printf("%lld\n",ans-dinic()+(int)1e9*n);
    return 0;
}