BZOJ 3112: [Zjoi2013]防守战线 ZKW费用流

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\),所以他的流量实际上是从汇点流出,流向源点,所以在判断这条边是否满流,统计费用时,是起点的费用是否等于终点的费用加上这条边的费用,我错了好久。

然而这道题更神仙,BZOJ 3112: [Zjoi2013]防守战线 ZKW费用流
所以我就不用多说什么了,当然,附上链接是必要的,全网仅此位大佬写了网络流算法: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;
}
上一篇:K大数查询[ZJOI2013]


下一篇:[ZJOI2013]丽洁体