[luogu3980]志愿者招募

标签：vis 志愿者 ans1 sum 招募 len luogu3980 int ll

记$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))$，可以通过

 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