【NOI2008】志愿者招募
和【2017山东day7】养猫做法类似。
都是神仙题。
首先我设\(c_{i,j}=[l[j]\leq i\leq r[j]]\) ，于是就可以列出下面的不等式：
\[\displaystyle
\begin{align}
\sum_{i=1}^mc_{1,i}*d_i&\geq a_1\\
&...\\
\sum_{i=1}^mc_{n,i}*d_i&\geq a_n\\
0&=0
\end{align}
\]
\begin{align}
\sum_{i=1}^mc_{1,i}*d_i&\geq a_1\\
&...\\
\sum_{i=1}^mc_{n,i}*d_i&\geq a_n\\
0&=0
\end{align}
\]
我们加一个辅助变量\(y_i\)，使不等式变成等式，并且在最后加上\(0=0\)：
\[\displaystyle
\begin{align}
\sum_{i=1}^mc_{1,i}*d_i&=y_1+a_1\\
&...\\
\sum_{i=1}^mc_{n,i}*d_i&=y_n+a_n\\
0&=0
\end{align}
\]
\begin{align}
\sum_{i=1}^mc_{1,i}*d_i&=y_1+a_1\\
&...\\
\sum_{i=1}^mc_{n,i}*d_i&=y_n+a_n\\
0&=0
\end{align}
\]
差分后：
\[\begin{align}
\displaystyle
\sum_{i=1}^mc_{1,i}*d_i&=y_1+a_1\\
\sum_{i=1}^mc_{2,i}*d_i+y_1+a_1&=\sum_{i=1}^mc_{1,i}*d_i+y_2+a_2\\
&...\\
\sum_{i=1}^mc_{n,i}*d_i+y_{n-1}+a_{n-1}
&=\sum_{i=1}^mc_{n-1,i}*d_i+y_n+a_n\\
y_n+a_n&=\sum_{i=1}^mc_{n,i}*d_i
\end{align}
\]
\displaystyle
\sum_{i=1}^mc_{1,i}*d_i&=y_1+a_1\\
\sum_{i=1}^mc_{2,i}*d_i+y_1+a_1&=\sum_{i=1}^mc_{1,i}*d_i+y_2+a_2\\
&...\\
\sum_{i=1}^mc_{n,i}*d_i+y_{n-1}+a_{n-1}
&=\sum_{i=1}^mc_{n-1,i}*d_i+y_n+a_n\\
y_n+a_n&=\sum_{i=1}^mc_{n,i}*d_i
\end{align}
\]
然后每个变量就会在等式左边和右边各出现一次。对于一个变量\(x\)，我们从它出现于右边的等式连一条边到它出现于左边的等式。对于常量，它出现在左边就从\(S\)连一条边到该等式，否则该等式连一条边到\(T\)。
代码：
#include<bits/stdc++.h>
#define ll long long
#define N 2005
#define M 20005
using namespace std;
inline int Get() {int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}while('0'<=ch&&ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;}
int n,m;
int S,T;
int l[M],r[M],c[M];
int a[N];
struct road {
int to,next;
int flow;
ll cost;
}s[(N+M)*5];
int h[N],cnt=1;
void add(int i,int j,int f,ll c) {
s[++cnt]=(road) {j,h[i],f,c};h[i]=cnt;
s[++cnt]=(road) {i,h[j],0,-c};h[j]=cnt;
}
ll ans=0;
ll tag[N];
ll lim[N];
ll dis[N];
int fr[N],e[N];
bool in[N];
queue<int>q;
int tot;
int maxflow;
bool ins[N];
int dfs(int v,int maxf) {
if(v==T) return maxf;
ins[v]=1;
int ret=0;
for(int i=h[v];i;i=s[i].next) {
int to=s[i].to;
if(!ins[to]&&s[i].flow&&dis[to]==dis[v]+s[i].cost) {
int dlt=dfs(to,min(maxf,s[i].flow));
ret+=dlt;
s[i].flow-=dlt;
s[i^1].flow+=dlt;
maxf-=dlt;
if(!maxf) return ins[v]=0,ret;
}
}
ins[v]=0;
return ret;
}
ll dinic() {
ll ans=0;
while(1) {
int tem=dfs(S,1e9);
if(!tem) break;
ans+=tem;
}
return ans;
}
bool spfa() {
memset(dis,0x3f,sizeof(dis));
dis[S]=0;
q.push(S);
while(!q.empty()) {
int v=q.front();
q.pop();
in[v]=0;
for(int i=h[v];i;i=s[i].next) {
int to=s[i].to;
if(s[i].flow&&dis[to]>dis[v]+s[i].cost) {
dis[to]=dis[v]+s[i].cost;
fr[to]=v;
e[to]=i;
if(!in[to]) in[to]=1,q.push(to);
}
}
}
if(dis[T]>1e9) return 0;
ans+=dinic()*dis[T];
return 1;
}
int main() {
n=Get(),m=Get();
for(int i=1;i<=n;i++) a[i]=Get();
for(int i=1;i<=m;i++) l[i]=Get(),r[i]=Get(),c[i]=Get();
T=n+2;
for(int i=1;i<=n;i++) {
add(i,T,a[i],0);
add(S,i+1,a[i],0);
add(i,i+1,1e9,0);
}
for(int i=1;i<=m;i++) {
add(r[i]+1,l[i],1e9,c[i]);
}
while(spfa());
cout<<ans;
return 0;
}