title
BZOJ 3112
LUOGU 3337
Description
战线可以看作一个长度为n 的序列,现在需要在这个序列上建塔来防守敌兵,在序列第i 号位置上建一座塔有Ci 的花费,且一个位置可以建任意多的塔,费用累加计算。有m 个区间[L1, R1], [L2, R2], …, [Lm, Rm],在第i 个区间的范围内要建至少Di 座塔。求最少花费。
Input
第一行为两个数n, m。
接下来一行,有n 个数,描述C 数组。
接下来m 行,每行三个数Li,Ri,Di,描述一个区间。
Output
仅包含一行,一个数,为最少花费。
Sample Input
5 3
1 5 6 3 4
2 3 1
1 5 4
3 5 2
Sample Output
11
HINT
【样例说明】
位置1 建2 个塔,位置3 建一个塔,位置4 建一个塔。花费1*2+6+3=11。
【数据规模】
对于20%的数据,n≤20,m≤20。
对于50%的数据(包括上部分的数据),Di 全部为1。
对于70%的数据(包括上部分的数据),n≤100,m≤1000。
对于100%的数据,n≤1000,m≤10000,1≤Li≤Ri≤n,其余数据均≤10000。
analysis
和志愿者招募简直一样,只不过是一个点可以贯穿许多区间。
网上大多数人都是线性规划单行纯算法,不过不会啊,而且,我们两个(其实是\(Chdy\))都看出了网络流模型了,难道不能写?
反正我要尝试一下,写了常用的\(EK\)版本费用流,然而被 \(T\) 飞。于是,我便想到了久闻大名的\(ZKW\)费用流,决定现学一下。
省略无数学习过程以及调试四个小时的过程
最后明白所谓\(ZKW\)费用流就是\(Dinic\)版费用流。需要倒挂 \(Spfa\),所以他的流量实际上是从汇点流出,流向源点,所以在判断这条边是否满流,统计费用时,是起点的费用是否等于终点的费用加上这条边的费用,我错了好久。
然而这道题更神仙,
所以我就不用多说什么了,当然,附上链接是必要的,全网仅此位大佬写了网络流算法:Zig_zag。
code
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e3+10,maxm=2e5+10,inf=INT_MAX;
char buf[1<<15],*fs,*ft;
inline char getc() { return (ft==fs&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),ft==fs))?0:*fs++; }
template<typename T>inline void read(T &x)
{
x=0;
T f=1, ch=getchar();
while (!isdigit(ch) && ch^'-') ch=getchar();
if (ch=='-') f=-1, ch=getchar();
while (isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48), ch=getchar();
x*=f;
}
template<typename T>inline void write(T x)
{
if (!x) { putchar('0'); return ; }
if (x<0) putchar('-'), x=-x;
T num=0, ch[20];
while (x) ch[++num]=x%10+48, x/=10;
while (num) putchar(ch[num--]);
}
int ver[maxm],edge[maxm],Next[maxm],cost[maxm],head[maxn],len=1;
inline void add(int x,int y,int z,int c)
{
ver[++len]=y,edge[len]=z,cost[len]=c,Next[len]=head[x],head[x]=len;
ver[++len]=x,edge[len]=0,cost[len]=-c,Next[len]=head[y],head[y]=len;
}
int s,t;
int dist[maxn];
bool vis[maxn];
inline void spfa()
{
for (int i=s; i<=t; ++i) dist[i]=-inf;
memset(vis,0,sizeof(vis));
queue<int>q;q.push(t);
dist[t]=0,vis[t]=1;
while (!q.empty())
{
int x=q.front();
q.pop();
vis[x]=0;
for (int i=head[x]; i; i=Next[i])
{
int y=ver[i];
if (edge[i^1] && dist[y]<dist[x]+cost[i^1])
{
dist[y]=dist[x]+cost[i^1];
if (!vis[y]) q.push(y),vis[y]=1;
}
}
}
}
int ans;//开long long会WA最后三个点,鬼知道为什么
inline int get(int x,int low)
{
if (x==t) { ans+=dist[s]*low; return low; }
int tmp=0;
vis[x]=1;
for (int i=head[x]; i; i=Next[i])
{
int y=ver[i];
if (edge[i] && !vis[y] && dist[x]==dist[y]+cost[i])
{
int a=get(y,min(low-tmp,edge[i]));
edge[i]-=a,edge[i^1]+=a,tmp+=a;
if (tmp==low) return tmp;
}
}
return tmp;
}
inline bool adjust()
{
int tmp=-inf;
for (int x=s; x<=t; ++x) if (vis[x])
for (int i=head[x]; i; i=Next[i])
{
int y=ver[i];
if (!vis[y] && edge[i]) tmp=max(tmp,dist[y]+cost[i]-dist[x]);
}
if (tmp==-inf) return false;
for (int i=s; i<=t; ++i) if (vis[i]) dist[i]+=tmp;
return true;
}
inline void zkw()
{
spfa();
do
do memset(vis,0,sizeof(vis));
while (get(s,inf));
while (adjust());
}
int c[maxn];
int main()
{
int n,m;
read(n);read(m);
s=0,t=n+2;
for (int i=1; i<=n; ++i) read(c[i]);
for (int i=1; i<=n+1; ++i)
if (c[i]-c[i-1]>0) add(s,i,c[i]-c[i-1],0);
else add(i,t,c[i-1]-c[i],0);
for (int i=1,x,y,z; i<=m; ++i) read(x),read(y),read(z),add(x,y+1,inf,z);
for (int i=1; i<=n; ++i) add(i,i+1,inf,0);
zkw();
write(ans);
return 0;
}