#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <deque>
#include <limits>
#include <string>
#include <sstream>
using namespace std;

const int oo_min=0xcfcfcfcf,oo_max=0x3f3f3f3f;

int n,m;
vector<int> a;
vector<int> f;
vector<int> e;
vector<int> u;
vector<int> pre;
vector<int> vis;
vector<vector<int> > c;
vector<vector<int> > p;
vector<vector<int> > ce;
vector<vector<int> > cw;
deque<int> q;

void add_edge_1(int x,int y,int c_v,int p_v)
{
    cw[x].push_back(y);
    c[x].push_back(c_v);
    p[x].push_back(p_v);
    ce[y].push_back(cw[x].size()-1);
    cw[y].push_back(x);
    c[y].push_back(0);
    p[y].push_back(-p_v);
    ce[x].push_back(cw[y].size()-1);
}

int bfs_1(int s,int t,int *flow,int *cost)
{
    f.resize(0);
    f.resize(cw.size(),0);
    f[s]=oo_max;
    e.resize(0);
    e.resize(cw.size(),-1);
    u.resize(0);
    u.resize(cw.size(),oo_max);
    u[s]=0;
    pre.resize(0);
    pre.resize(cw.size(),-1);
    pre[s]=s;
    vis.resize(0);
    vis.resize(cw.size(),0);
    for (q.resize(0),vis[s]=1,q.push_back(s);(!q.empty());vis[q.front()]=0,q.pop_front())
    {
        int now=q.front();
        for (int i=0;i<cw[now].size();i++)
            if (c[now][i]&&u[now]+p[now][i]<u[cw[now][i]])
            {
                f[cw[now][i]]=min(c[now][i],f[now]);
                e[cw[now][i]]=i;
                u[cw[now][i]]=u[now]+p[now][i];
                pre[cw[now][i]]=now;
                if (vis[cw[now][i]]==0)
                    vis[cw[now][i]]=1,q.push_back(cw[now][i]);
            }
    }
    (*flow)=f[t];
    (*cost)=u[t];
    return (pre[t]!=-1);
}

void min_cost_max_flow_1(int s,int t,int *flow,int *cost)
{
    int temp_flow,temp_cost;
    while (bfs_1(s,t,&temp_flow,&temp_cost))
    {
        for (int i=t;i!=s;i=pre[i])
            c[pre[i]][e[i]]-=temp_flow,c[i][ce[pre[i]][e[i]]]+=temp_flow;
        (*flow)+=temp_flow;
        (*cost)+=(temp_cost*temp_flow);
    }
}

int main()
{
    while (~scanf("%d%d",&n,&m))
    {
        cw.resize(0);
        cw.resize(n+3);
        ce.resize(0);
        ce.resize(cw.size());
        c.resize(0);
        c.resize(cw.size());
        p.resize(0);
        p.resize(cw.size());
        for (int i=0;i<cw.size();i++)
        {
            cw[i].resize(0);
            ce[i].resize(0);
            c[i].resize(0);
            p[i].resize(0);
        }
        a.resize(0);
        a.resize(n+2,0);
        for (int i=1;i<=n;i++)
            scanf("%d",&a[i]);
        for (int i=1;i<=m;i++)
        {
            int a,b,c;
            scanf("%d%d%d",&a,&b,&c);
            add_edge_1(a,b+1,oo_max,c);
        }
        for (int i=1;i<=n+1;i++)
        {
            int flow=a[i]-a[i-1];
            if (flow>0)
                add_edge_1(0,i,flow,0);
            else if (flow<0)
                add_edge_1(i,cw.size()-1,-flow,0);
            if (i>1)
                add_edge_1(i,i-1,oo_max,0);
        }
        int ans_flow=0,ans_cost=0;
        min_cost_max_flow_1(0,cw.size()-1,&ans_flow,&ans_cost);
        printf("%d\n",ans_cost);
    }
}

看成线性规划，对偶之后可以证明得到的矩阵是全幺模的，直接单纯形。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXSIZE=10000020;
const ll INF=0x3f3f3f3f3f3f3f3fLL;
int bufpos;
char buf[MAXSIZE];
#define NEG 0
void init(){
    #ifdef LOCAL
        freopen("1061.txt","r",stdin);
    #endif
    buf[fread(buf,1,MAXSIZE,stdin)]='\0';
    bufpos=0;
}
#if NEG
int readint(){
    bool isneg;
    int val=0;
    for(;!isdigit(buf[bufpos]) && buf[bufpos]!='-';bufpos++);
    bufpos+=(isneg=buf[bufpos]=='-');
    for(;isdigit(buf[bufpos]);bufpos++)
        val=val*10+buf[bufpos]-'0';
    return isneg?-val:val;
}
#else
int readint(){
    int val=0;
    for(;!isdigit(buf[bufpos]);bufpos++);
    for(;isdigit(buf[bufpos]);bufpos++)
        val=val*10+buf[bufpos]-'0';
    return val;
}
#endif
char readchar(){
    for(;isspace(buf[bufpos]);bufpos++);
    return buf[bufpos++];
}
int readstr(char* s){
    int cur=0;
    for(;isspace(buf[bufpos]);bufpos++);
    for(;!isspace(buf[bufpos]);bufpos++)
        s[cur++]=buf[bufpos];
    s[cur]='\0';
    return cur;
}
int n,m;
ll a[10005][1005];
void pivot(int e,int l){ //e,n+l;
    ll tmp=-a[l][e];
    a[l][e]=-1;
    for(int i=0;i<=n;i++)
        a[l][i]/=tmp;
    for(int i=0;i<=m;i++)
        if (i!=l && a[i][e]){
            ll tmp=a[i][e];
            a[i][e]=0;
            if (tmp==1)
                for(int j=0;j<=n;j++)
                    a[i][j]+=a[l][j];
            else if (tmp==-1)
                for(int j=0;j<=n;j++)
                    a[i][j]-=a[l][j];
            else for(int j=0;j<=n;j++)
                a[i][j]+=tmp*a[l][j];
        }
}
ll work(){
    while(1){
        ll mx=0,x=0;
        for(int i=1;i<=n;i++)
            if (a[0][i]>mx)
                mx=a[0][i],x=i;
        if (!x)
            return a[0][0];
        ll mn=INF,y=0;
        for(int i=1;i<=m;i++){
            if (a[i][x]>=0)
                continue;
            ll tmp=-a[i][0]/a[i][x];
            if (tmp<mn)
                mn=tmp,y=i;
        }
        if (!y){
            puts("WTF");
            return INF;
        }
        pivot(x,y);
    }
}
int main(){
    init();
    n=readint(),m=readint();
    for(int i=1;i<=n;i++)
        a[0][i]=readint();
    for(int i=1;i<=m;i++){
        int l=readint(),r=readint();
        a[i][0]=readint();
        for(int j=l;j<=r;j++)
            a[i][j]=-1;
    }
    printf("%lld",work());
}

神奇的费用流....
Orz楼下学长QwQ

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1005, MAXM = 200000; 
struct node {
    int to, next, f, c, neg;
} edge[MAXM];
int head[MAXN], top = 0;
void push(int i, int j, int k, int l)
{
    //printf("%d--%d,%d-->%d\n", i, k, l, j);
    ++top, edge[top] = (node) {j, head[i], k, l, top+1}, head[i] = top;
    ++top, edge[top] = (node) {i, head[j], 0, -l, top-1}, head[j] = top;
}
int n, m;
int S = 1002, T = 1003;
const int inf = 23333333;

void push_lim(int i, int j, int low)
{
    push(S, j, low, 0);
    push(i, T, low, 0);
    push(i, j, inf, 0);
}

int vis[MAXN], dis[MAXN];
int pre[MAXN], pre_edge[MAXN];
queue<int> que;

bool spfa()
{
    memset(vis, 0, sizeof vis);
    memset(dis, 127/3, sizeof dis);
    memset(pre, 0, sizeof pre);
    vis[S] = 1, dis[S] = 0, que.push(S);
    while (!que.empty()) {
        int tp = que.front(); que.pop(); vis[tp] = 0;
        for (int i = head[tp]; i; i = edge[i].next) {
            if (edge[i].f == 0 || dis[edge[i].to] <= dis[tp] + edge[i].c) continue;
            dis[edge[i].to] = dis[tp] + edge[i].c;
            pre[edge[i].to] = tp;
            pre_edge[edge[i].to] = i;
            if (!vis[edge[i].to])
                vis[edge[i].to] = 1, que.push(edge[i].to);
        }
    }
    return dis[T] <= inf;
}

int work(int &cost)
{
    int ans = inf;
    for (int i = T; i != S; i = pre[i]) ans = min(ans, edge[pre_edge[i]].f);
    for (int i = T; i != S; i = pre[i]) edge[pre_edge[i]].f -= ans, edge[edge[pre_edge[i]].neg].f += ans;
    cost += dis[T]*ans;
    //cout << dis[T] << "--" << endl;
    //cin.get();
    return ans;
}

int mcf(int &cost)
{
    int ans = 0;
    while (spfa()) ans += work(cost);
    return ans; 
}

int main() 
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        int u; scanf("%d", &u);
        push_lim(i, i+1, u);
    }
    for (int i = 1; i <= m; i++) {
        int s, t, c; scanf("%d%d%d", &s, &t, &c);
        push(t+1, s, inf, c);
    }
    int cost = 0;
    mcf(cost);
    cout << cost << endl; 
    return 0;
}

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>

const int maxN=1005;
const int maxM=10005;
const int inf=0x7f7f7f7f;

struct Edge
{
int to;
int next;
int capacity;
int cost;

void assign(int t,int n,int cp,int co)
{
to=t,next=n,capacity=cp,cost=co;
}
};

Edge elist[maxM*20];
int head[maxN];
int ecnt;
int src,sink;

void initEdge()
{
memset(head,-1,sizeof(head));
ecnt=0;
}

inline void addEdge(int from,int to,int capacity,int cost)
{
elist[ecnt].assign(to,head[from],capacity,cost);
head[from]=ecnt++;
elist[ecnt].assign(from,head[to],0,-cost);
head[to]=ecnt++;
}

int N,M;
int A[maxN];
int S[maxM],T[maxM],C[maxM];

void input()
{
scanf("%d%d",&N,&M);
A[0]=0; A[N+1]=0;
for(int i=1;i<=N;i++) scanf("%d",A+i);
for(int i=1;i<=M;i++)
scanf("%d%d%d",S+i,T+i,C+i);
}

void buildGraph()
{
src=0; sink=N+2;
initEdge();
for(int i=1;i<=N+1;i++)
{
if(A[i]-A[i-1]>0) addEdge(i,sink,A[i]-A[i-1],0);
else if(A[i]-A[i-1]<0) addEdge(src,i,A[i-1]-A[i],0);
}
for(int i=1;i<=N;i++)
addEdge(i,i+1,inf,0);
for(int i=1;i<=M;i++)
addEdge(T[i]+1,S[i],inf,C[i]);
}

int dist[maxN];
int prevV[maxN];
int prevE[maxN];
bool inq[maxN];
std::queue<int> que;

bool spfa()
{
memset(dist,0x7f,sizeof(dist));
dist[src]=0;
memset(inq,0,sizeof(inq));
que.push(src);
prevV[src]=prevE[src]=-1;
while(!que.empty())
{
int cur=que.front();
que.pop(); inq[cur]=false;
for(int e=head[cur];e!=-1;e=elist[e].next)
if(elist[e].capacity)
{
int& to=elist[e].to;
int& co=elist[e].cost;
if(dist[to]>dist[cur]+co)
{
dist[to]=dist[cur]+co;
prevV[to]=cur;
prevE[to]=e;
if(!inq[to])
{
que.push(to);
inq[to]=true;
}
}
}
}
return dist[sink]<inf;
}

int minCostFlow()
{
int res(0);
while(spfa())
{
int maxf=inf;
for(int e=prevE[sink],v=sink;e!=-1;v=prevV[v],e=prevE[v])
maxf=std::min(maxf,elist[e].capacity);
for(int e=prevE[sink],v=sink;e!=-1;v=prevV[v],e=prevE[v])
{
res+=maxf*elist[e].cost;
elist[e].capacity-=maxf;
elist[e^1].capacity+=maxf;
}
}
return res;
}

int main()
{
input();
buildGraph();
printf("%d\n",minCostFlow());
return 0;
}

Orz ByVoid大神

建模好难想得到，费用流……
```c++
#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;

const int INF=2147483647;

struct Ed
{
int from,to,cap,cost,flow;
Ed(int a,int b,int c=INF,int e=0,int d=0) : from(a),to(b),cap(c),cost(e),flow(d) {};
};

struct Po
{
int th;
vector<int > id_edges;
Po(int a) : th(a) {};
};

int n,m;
long long int all_cost=0;
int a[1100],c[1100],p[1100],leastpe[1100];
vector<Ed> edges;
vector<Po> points;
bool inqu[1100];

void add_edges(int from,int to,int cap,int cost)
{
edges.push_back(Ed(from,to,cap,cost));
points[from].id_edges.push_back(edges.size()-1);
edges.push_back(Ed(to,from,0,-1*cost));
points[to].id_edges.push_back(edges.size()-1);
/*return points[from].id_edges[points[from].id_edges.size()-1];*/
}

bool SPFA()
{
memset(a,0,sizeof(a));
memset(c,-1,sizeof(c));
memset(p,0,sizeof(p));
memset(inqu,0,sizeof(inqu));
queue<int> Q;
a[0]=INF; c[0]=0;
Q.push(0); inqu[0]=true;
while(!Q.empty())
{
int k=Q.front();Q.pop(); inqu[k]=false;
Po &now=points[k];

for(int i=0;i<(int)now.id_edges.size();i++)
{
Ed &now_ed=edges[now.id_edges[i]];
if(now_ed.flow<now_ed.cap&&(c[now_ed.to]==-1||c[now_ed.to]>c[now.th]+now_ed.cost))
{
a[now_ed.to]=min(a[now.th],now_ed.cap-now_ed.flow);
p[now_ed.to]=now.id_edges[i];
c[now_ed.to]=c[now.th]+now_ed.cost;
if(!inqu[now_ed.to]) { Q.push(now_ed.to); inqu[now_ed.to] =true; }
}
}
}
if(a[n+2]==0) return false;
all_cost+=(long long int)a[n+2]*(long long int)c[n+2];
for(int i=n+2;i!=0;i=edges[p[i]].from)
{
edges[p[i]].flow+=a[n+2];
edges[p[i]^1].flow-=a[n+2];
}
return true;
}

int main()
{
/*freopen("employee.in","r",stdin);*/
memset(leastpe,0,sizeof(leastpe));
scanf("%d%d",&n,&m);
points.push_back(Po(0));
for(int i=1;i<=n;i++)
{
scanf("%d",&leastpe[i]);
points.push_back(Po(i));
}
points.push_back(Po(n+1));points.push_back(Po(n+2));
for(int i=1;i<=n+1;i++)
if(leastpe[i]-leastpe[i-1]>0) add_edges(i,n+2,(leastpe[i]-leastpe[i-1]),0);
else if(leastpe[i]-leastpe[i-1]<0) add_edges(0,i,(leastpe[i]-leastpe[i-1])*(-1),0);
for(int i=1;i<=m;i++)
{
int b,e,c;
scanf("%d%d%d",&b,&e,&c);
add_edges(e+1,b,INF,c);
/*workgroup_id[i]=add_edges(e+1,b,INF,c);*/
}
for(int i=2;i<=n+1;i++) add_edges(i-1,i,INF,0);

while(SPFA()) {}

printf("%lld\n",all_cost);
return 0;
}
```

这题的难度是10？第一次见到,一直以为4就是最高了。。。 ZKW费用流。。。
编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 564 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 564 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 560 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 576 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 608 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 648 KiB, score = 10
测试数据 #6: Accepted, time = 15 ms, mem = 860 KiB, score = 10
测试数据 #7: Accepted, time = 31 ms, mem = 1020 KiB, score = 10
测试数据 #8: Accepted, time = 46 ms, mem = 1236 KiB, score = 10
测试数据 #9: Accepted, time = 93 ms, mem = 1728 KiB, score = 10
Accepted, time = 185 ms, mem = 1728 KiB, score = 100
#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

#define MAXN 1010

struct node {
int t,f,c;
node *next,*pair;
node (){
next=pair=NULL;
}
};

node *head[MAXN];

void INSERT(int s,int t,int f,int c){
node *p=new(node);
p->t=t;
p->f=f;
p->c=c;
p->next=head[s];
head[s]=p;
p=new(node);
p->t=s;
p->f=0;
p->c=-c;
p->next=head[t];
head[t]=p;
head[s]->pair=head[t];
head[t]->pair=head[s];
}

int n,m;
int S,T;
int a[MAXN];

int dist[MAXN];
bool f[MAXN];
int cost=0;

int aug(int v,int flow){
if (v==T){
cost+=flow*dist[S];
return flow;
}
f[v]=false;
int rec=0;
for (node *p=head[v];p;p=p->next){
if (p->f&&f[p->t]&&dist[v]==dist[p->t]+p->c){
int ret=aug(p->t,min(flow-rec,p->f));
p->f-=ret;
p->pair->f+=ret;
if ((rec+=ret)==flow){
return flow;
}
}
}
return rec;
}

bool relabel(){
int delta=0x7fffffff;
for (int i=0;i++<T;){
if (!f[i]){
for (node *p=head[i];p;p=p->next){
if (p->f&&f[p->t]){
delta=min(delta,dist[p->t]+p->c-dist[i]);
}
}
}
}
if (delta==0x7fffffff){
return false;
}
for (int i=0;i++<T;){
if (!f[i]){
dist[i]+=delta;
}
}
return true;
}

int main(){
memset(head,0,sizeof(head));
scanf("%d%d",&n,&m);
S=n+2;
T=S+1;
int x=0;
for (int i=0;i++<n;){
scanf("%d",&a[i]);
if (a[i]-x>=0){
INSERT(S,i,a[i]-x,0);
} else INSERT(i,T,x-a[i],0);
x=a[i];
}
INSERT(n+1,T,a[n],0);
for (int i=0;i++<m;){
int s,t,c;
scanf("%d%d%d",&s,&t,&c);
INSERT(s,t+1,0x7fffffff,c);
}
for (int i=1;i++<n+1;){
INSERT(i,i-1,0x7fffffff,0);
}
memset(dist,0,sizeof(dist));
do {
do {
memset(f,true,sizeof(f));
} while (aug(S,0x7fffffff));
} while (relabel());
printf("%d\n",cost);
return 0;
}