Solution
把志愿者想象成积木,那么就是在一条数轴上每个位置搭上特定高度的积木
那么也可以转化成在数轴上每个位置挖特定深度的坑,最后填平,志愿者是土
先把坑挖好,add(i,i+1,inf-a[i],0)
然后填坑只能用土,add(s[i],t[i]+1,inf,c[i])
跑最小费用最大流
Code
#include <cstdio> #include <cstdlib> #include <queue> #include <cstring> #include <algorithm> using namespace std; const int N=1e4+10,M=4e4; int mc,mf,n,m,s,t,a[N],l[N],r[N],c[N],inf=1<<30; int head[N],ver[M],nxt[M],edge[M],cost[M],tot=1; void add(int u,int v,int w,int c) { ver[++tot]=v,nxt[tot]=head[u],edge[tot]=w,cost[tot]=c,head[u]=tot; ver[++tot]=u,nxt[tot]=head[v],edge[tot]=0,cost[tot]=-c,head[v]=tot; } int incf[N],pre[N],dis[N],in[N]; bool spfa() { memset(dis,0x3f,sizeof(dis)); queue <int> q; dis[s]=0,pre[t]=-1,incf[s]=inf; q.push(s); while(!q.empty()) { int u=q.front(); q.pop(); in[u]=0; for(int i=head[u],v;i;i=nxt[i]) if(edge[i]>0 && dis[v=ver[i]]>dis[u]+cost[i]) { dis[v]=dis[u]+cost[i]; pre[v]=i,incf[v]=min(incf[u],edge[i]); if(!in[v]) in[v]=1,q.push(v); } } return pre[t]!=-1; } void update() { mf+=incf[t],mc+=incf[t]*dis[t]; int x=t; while(x!=s) { int i=pre[x]; edge[i]-=incf[t],edge[i^1]+=incf[t]; x=ver[i^1]; } } int main() { scanf("%d%d",&n,&m); s=0,t=n+1; add(s,1,inf,0); for(int i=1;i<=n;i++) scanf("%d",&a[i]),add(i,i+1,inf-a[i],0); for(int i=1;i<=m;i++) { scanf("%d%d%d",&l[i],&r[i],&c[i]); add(l[i],r[i]+1,inf,c[i]); } while(spfa()) update(); printf("%d\n",mc); return 0; }
原文:https://www.cnblogs.com/hsez-cyx/p/12880084.html