记$x_{i}$为第$i$类志愿者数量$,y_{j}=\sum_{j\in [s_{i},t_{i}]}x_{i}-a_{j}$,则问题即
$$
\forall i\in [1,m],x_{i}\ge 0\\
\forall j\in [1,n],y_{j}\ge 0\\
y_{1}-\sum_{s_{i}=1}x_{i}=-a_{1}\\\sum_{t_{i}=n}x_{i}-y_{n}=a_{n}\\
\forall j\in [2,n],y_{j}+\sum_{t_{i}=j-1}x_{j}-y_{j-1}-\sum_{s_{i}=j}x_{i}=a_{j-1}-a_{j}\\
\min \sum_{i=1}^{m}c_{i}x_{i}
$$
显然可以转化为费用流,具体方式参考[loj6079]养猫
时间复杂度为$o({\rm MCMF}(n,m))$,可以通过
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 namespace MCMF{ 5 const int N=1005,M=20005; 6 int S,T,E,head[N],vis[N],from[N]; 7 ll ans1,ans2,d[N];queue<int>q; 8 struct edge{ 9 int nex,to;ll len,cost; 10 }e[M<<1]; 11 void init(){ 12 E=0; 13 memset(head,-1,sizeof(head)); 14 } 15 void add(int x,int y,ll z,ll w){ 16 e[E]=edge{head[x],y,z,w},head[x]=E++; 17 e[E]=edge{head[y],x,0,-w},head[y]=E++; 18 } 19 bool spfa(){ 20 memset(d,0x3f,sizeof(d)); 21 d[S]=0,q.push(S); 22 while (!q.empty()){ 23 int k=q.front();q.pop(); 24 for(int i=head[k];i!=-1;i=e[i].nex){ 25 int u=e[i].to; 26 if ((e[i].len)&&(d[u]>d[k]+e[i].cost)){ 27 d[u]=d[k]+e[i].cost,from[u]=i; 28 if (!vis[u])q.push(u),vis[u]=1; 29 } 30 } 31 vis[k]=0; 32 } 33 return d[T]<=1e18; 34 } 35 pair<ll,ll> query(int s,int t){ 36 S=s,T=t,ans1=ans2=0; 37 while (spfa()){ 38 ll s=1e18; 39 for(int i=T;i!=S;i=e[from[i]^1].to)s=min(s,e[from[i]].len); 40 ans1+=s,ans2+=s*d[T]; 41 for(int i=T;i!=S;i=e[from[i]^1].to){ 42 e[from[i]].len-=s; 43 e[from[i]^1].len+=s; 44 } 45 } 46 return make_pair(ans1,ans2); 47 } 48 }; 49 const int N=1005; 50 int n,m,s,t,c,a[N]; 51 int main(){ 52 using namespace MCMF; 53 init(); 54 scanf("%d%d",&n,&m); 55 for(int i=1;i<=n;i++){ 56 scanf("%d",&a[i]); 57 add(i,i+1,1e18,0); 58 } 59 for(int i=1;i<=m;i++){ 60 scanf("%d%d%d",&s,&t,&c); 61 add(t+1,s,1e18,c); 62 } 63 add(1,n+2,a[1],0),add(0,n+1,a[n],0); 64 for(int i=2;i<=n;i++){ 65 if (a[i-1]-a[i]>0)add(0,i,a[i-1]-a[i],0); 66 else add(i,n+2,a[i]-a[i-1],0); 67 } 68 printf("%lld\n",query(0,n+2).second); 69 return 0; 70 }View Code
标签:vis,志愿者,ans1,sum,招募,len,luogu3980,int,ll From: https://www.cnblogs.com/PYWBKTDA/p/16734468.html