P7730 [JDWOI-1] 蜀道难

FxorG · 2021-12-10 21:19:05 · 题解

为什么这题还不错却没人写题解啊。

考虑序列不降时有什么性质：a_i-a_{i-1}\ge0,i\in(1,n]

考虑操作是区间同时加减，想到差分。

记 d_1=a_1,d_i=a_i-a_{i-1},i\in(1,n]，那么我们要让 d_i\ge0,i\in[1,n]

每次操作即

di--,dj++
di++,dj--

那么对于 d_i>0 的，可以最多减 d_i 次，提供 d_i 次加的机会，对于 d_i<0 的，至少被加 |d_i| 次，需要 d_i 次被加。显然转化为二分图之后最小费用最大流。

但是假如只规定正权点向负权点提供流量是不够的，因为可能长度无法匹配导致我们对于 i,j,d_i>0,d_j<0 需要 k 来先让 i,k 操作，再让 k,j 操作来实现。

所以我们要对于每个区间，无论左右是什么点，都连。

代码

#include <bits/stdc++.h>
using namespace std;
int rd() {
    int f=1,sum=0; char ch=getchar();
    while(!isdigit(ch)) {if(ch=='-') f=-1; ch=getchar();}
    while(isdigit(ch)) {sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();}
    return sum*f;
}

#define N (int)(5e4+5)
#define inf (int)(2e9)
struct edge {
    int nex,to,w,c;
}e[N<<1];
int hea[N],cnt=1;
int mic[2][N],bian[N];
int n,m,S,T,tot,a[N],b[N],ans;

void add_edge(int x,int y,int z,int c) {
    e[++cnt].nex=hea[x]; e[cnt].to=y; e[cnt].w=z; e[cnt].c=c; hea[x]=cnt;
}

void add(int x,int y,int z,int c) {
    add_edge(x,y,z,c); add_edge(y,x,0,-c);
}

deque<int>q;
bool vis[N];
int dis[N];
bool spfa() {
    for(int i=0;i<N;i++) dis[i]=inf,vis[i]=0;
    q.push_back(S); dis[S]=0;
    while(!q.empty()) {
        int x=q.front(); q.pop_front();
        vis[x]=0;
        for(int i=hea[x];i;i=e[i].nex) {
            int y=e[i].to;
            if(e[i].w&&dis[y]>dis[x]+e[i].c) {
                dis[y]=dis[x]+e[i].c;
                if(!vis[y]) {
                    vis[y]=1;
                    if(!q.empty()&&dis[y]<dis[q.front()]) q.push_front(y);
                    else q.push_back(y);
                }
            }
        }
    }
    return dis[T]<inf;
}

int dfs(int x,int lim) {
    if(x==T||!lim) return lim;
    int flow=0,fl;
    vis[x]=1;
    for(int i=hea[x];i&&lim;i=e[i].nex) {
        int y=e[i].to;
        if(e[i].w&&!vis[y]&&dis[y]==dis[x]+e[i].c) {
            fl=dfs(y,min(lim,e[i].w));
            if(!fl) continue;
            flow+=fl; lim-=fl; e[i].w-=fl; e[i^1].w+=fl;
        //  cout<<e[i].c<<" "<<fl<<endl;
            ans+=e[i].c*fl;
        }
    }
    if(!flow) dis[x]=inf;
    vis[x]=0;
    return flow;
}

void dinic() {
    while(spfa()) {
        memset(vis,0,sizeof(vis));
        dfs(S,inf);
    }
}

int main() {
    n=rd(); m=rd(); S=0; T=n+2;
    for(int i=1;i<=n;i++) b[i]=rd();
    for(int i=1;i<=n;i++) a[i]=b[i]-b[i-1];
    for(int i=0;i<=n+1;i++) mic[0][i]=mic[1][i]=inf;
    char op; int x,y;
    for(int i=1;i<=m;i++) {
        cin>>op; x=rd(); y=rd();
        if(op=='+') op=0; else op=1;
        mic[op][x]=min(mic[op][x],y);
    }
    add(S,n+1,inf,0);
    for(int i=1;i<=n;i++) {
        if(a[i]>0) {
            add(S,i,a[i],0);
        } else {
            add(i,T,-a[i],0); bian[++tot]=cnt-1;
        }
    }
    for(int i=1;i<=n;i++) {
        for(int l=1,r=l+i;r<=n+1;l++,r=l+i) {
            if(mic[0][i]<inf) add(r,l,inf,mic[0][i]);
            if(mic[1][i]<inf) add(l,r,inf,mic[1][i]);
        }
    }
    dinic();
    for(int i=1;i<=tot;i++) {
        if(e[bian[i]].w) {
            printf("-1"); return 0;
        }
    }
    printf("%d",ans);
    return 0;
}