[loj6079]养猫

以下线性规划问题，可以转化为费用流：

• 有$m$个变量，有限制$x_{i}\in [0,r_{i}]\cap N$
• 有$n$个等式，每个等式形如$\sum_{i\in U_{j}}x_{i}-\sum_{i\in V_{j}}x_{i}=C_{j}$
• 目标函数为$\sum_{i=1}^{m}c_{i}x_{i}$（以下均以最大化为例）
• $\{U_{j}\}$两两不交且$\bigcup_{j=1}^{n}U_{j}=[1,m]$（$\{V_{j}\}$同理）

具体的，转化方式如下：

• 建立$n+2$个点（包含$S,T$），每个点对应于一个等式
• 对于每个变量$x_{i}$，假设$i\in U_{j_{1}},V_{j_{2}}$，建边$(j_{1},j_{2},r_{i},c_{i})$
• 对于$C_{j}>0$，建边$(S,j,C_{j},0)$；对于$C_{j}<0$，建边$(j,T,-C_{j},0)$
• 跑最大费用最大流，若流量$<\sum_{j=1}^{n}\max(C_{j},0)$则无解，否则答案为费用

回到原问题，记$x_{i}$表示第$i$​个天是否睡觉，问题即
$$
\forall i\in [1,n],x_{i}\in [0,1]\\\forall i\in [1,n-k+1],\sum_{j=i}^{i+k-1}x_{j}\in [l,r]\\\max\sum_{i=1}^{n}(s_{i}-e_{i})x_{i}
$$
（其中$l=ms,r=k-me$）

考虑第$2$个限制，将左半部分$-l$作为变量$A_{i}$，问题也即
$$
\forall i\in [1,n],x_{i}\in [0,1]\\\forall i\in [1,n-k+1],A_{i}\in [0,r-l]\\
\sum_{i=1}^{k}x_{i}-A_{1}=l\\A_{n-k+1}-\sum_{i=n-k+1}^{n}x_{i}=-l\\\forall i\in [1,n-k],A_{i}+x_{i+k}-A_{i+1}-x_{i}=0\\
\max\sum_{i=1}^{n}(s_{i}-e_{i})x_{i}
$$
显然可以转化为费用流，具体方式参考前者

注意可能有负环，可以转换为上下界费用流后处理

时间复杂度为$o({\rm MCMF}(n,n))$，可以通过

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 typedef long long ll;
  4 namespace MCMF_bounds{
  5     const int N=1005,M=2005;
  6     int S,T,E,head[N],vis[N],from[N];
  7     ll sum,ans1,ans2,cnt[N],d[N];queue<int>q;
  8     struct edge{
  9         int nex,to;ll len,cost;
 10     }e[N+M<<1];
 11     void init(){
 12         E=sum=0;
 13         memset(head,-1,sizeof(head));
 14         memset(cnt,0,sizeof(cnt));
 15     }
 16     void add(int x,int y,ll z,ll w){
 17         if (w>=0){
 18             e[E]=edge{head[x],y,z,w},head[x]=E++;
 19             e[E]=edge{head[y],x,0,-w},head[y]=E++;
 20         }
 21         else{
 22             sum+=z*w,cnt[x]-=z,cnt[y]+=z;
 23             e[E]=edge{head[x],y,0,w},head[x]=E++;
 24             e[E]=edge{head[y],x,z,-w},head[y]=E++;
 25         }
 26     }
 27     void add(int x,int y,ll zl,ll zr,ll w){
 28         sum+=zl*w,cnt[x]-=zl,cnt[y]+=zl;
 29         e[E]=edge{head[x],y,zr-zl,w},head[x]=E++;
 30         e[E]=edge{head[y],x,0,-w},head[y]=E++;
 31     }
 32     bool spfa(){
 33         memset(d,0x3f,sizeof(d));
 34         d[S]=0,q.push(S);
 35         while (!q.empty()){
 36             int k=q.front();q.pop();
 37             for(int i=head[k];i!=-1;i=e[i].nex){
 38                 int u=e[i].to;
 39                 if ((e[i].len)&&(d[u]>d[k]+e[i].cost)){
 40                     d[u]=d[k]+e[i].cost,from[u]=i;
 41                     if (!vis[u])q.push(u),vis[u]=1;
 42                 }
 43             }
 44             vis[k]=0;
 45         }
 46         return d[T]<=1e18;
 47     }
 48     pair<ll,ll> query(int s,int t){
 49         S=N-2,T=N-1,ans1=0,ans2=sum;
 50         for(int i=0;i<N;i++){
 51             if (cnt[i]>0)add(S,i,0,cnt[i],0),ans1+=cnt[i];
 52             if (cnt[i]<0)add(i,T,0,-cnt[i],0);
 53         }
 54         add(t,s,0,1e18,0);
 55         while (spfa()){
 56             ll s=1e18;
 57             for(int i=T;i!=S;i=e[from[i]^1].to)s=min(s,e[from[i]].len);
 58             ans1-=s,ans2+=s*d[T];
 59             for(int i=T;i!=S;i=e[from[i]^1].to){
 60                 e[from[i]].len-=s;
 61                 e[from[i]^1].len+=s;
 62             }
 63         }
 64         if (ans1)return make_pair(-1,0);
 65         S=s,T=t,ans1=e[E-1].len;
 66         for(int i=0;i<N;i++)
 67             if (cnt[i])head[i]=e[head[i]].nex;
 68         while (spfa()){
 69             ll s=1e18;
 70             for(int i=T;i!=S;i=e[from[i]^1].to)s=min(s,e[from[i]].len);
 71             ans1+=s,ans2+=s*d[T];
 72             for(int i=T;i!=S;i=e[from[i]^1].to){
 73                 e[from[i]].len-=s;
 74                 e[from[i]^1].len+=s;
 75             }
 76         }
 77         return make_pair(ans1,ans2);
 78     }
 79 };
 80 const int N=1005;
 81 int n,k,l,r,a[N],b[N],pos[N];
 82 int main(){
 83     using namespace MCMF_bounds;
 84     init();
 85     scanf("%d%d%d%d",&n,&k,&l,&r);
 86     r=k-r;
 87     for(int i=1;i<=n;i++)scanf("%d",&a[i]);
 88     for(int i=1;i<=n;i++)scanf("%d",&b[i]);
 89     int S=n-k+2,T=n-k+3;
 90     add(n-k+2,0,l,0),add(n-k+1,n-k+3,l,0);
 91     for(int i=1;i<=n-k+1;i++)add(i,i-1,r-l,0);
 92     for(int i=1;i<=n;i++){
 93         pos[i]=E;
 94         add(max(i-k,0),min(i,n-k+1),1,b[i]-a[i]);
 95     }
 96     ll ans=-query(n-k+2,n-k+3).second;
 97     for(int i=1;i<=n;i++)ans+=b[i];
 98     printf("%lld\n",ans);
 99     for(int i=1;i<=n;i++){
100         if (e[pos[i]].len)putchar('E');
101         else putchar('S');
102     }
103     return 0;
104 }