团圆

网络流

题面

有$n$个站台,每个站台距第一个站台的距离为$s_i$公里。一列火车，上有$k$个座位。$q$位乘客，乘坐火车区间为$(l_i,r_i)$。
设代价为每公里火车上空置座位数之和。
最小化代价，并最大化乘车人数。
（输出代价占$40\%$、最大人数乘车方案占$20\%$、怎样安排都有车坐的人占$40\%$）

• $30pts\ k=1$
• $100pts\ n\leq500,q\leq3500$

解析

$30pts$算法

大力$DP$即可。
不过这个$DP$看起来好神仙。

• 通过挂链，把乘客编号挂在右端点上，以找到左端点进行转移。
• 状态用$bitset$维护。
  。。。

记得一位$bitset$只占$1/8$字节。

#include<bits/stdc++.h>
#define ll long long
#define rg register
using namespace std;
const int MAXN=3510;
struct gao{   int Le,Ri;   }App[MAXN];
struct zhang{   int Maxs;   bitset<MAXN>Tra,Mst;   }Ans;
int n,k,q,A[MAXN],Maxv;
struct yi{
    zhang Dp[MAXN];   int First[MAXN],Next[MAXN];
    inline void Solve()
        {   for(rg int i=0;i<=n;i++) First[i]=-1;
            for(rg int i=1;i<=n;i++) A[i]+=A[i-1];
            for(rg int i=1;i<=q;i++)
                Next[i]=First[App[i].Ri],First[App[i].Ri]=i;
            for(rg int i=1;i<=n;i++)
            {   Dp[i]=Dp[i-1];
                for(rg int j=First[i];j!=-1;j=Next[j])
                {   zhang Now=Dp[App[j].Le];    Now.Tra[j]=1,Now.Mst[j]=1;
                    Now.Maxs+=A[App[j].Ri]-A[App[j].Le];
                    if(Now.Maxs<Dp[i].Maxs)  continue ;
                    if(Now.Maxs==Dp[i].Maxs&&Now.Tra.count()<Dp[i].Tra.count())  continue ;
                    if(Now.Maxs>Dp[i].Maxs||Now.Tra.count()>Dp[i].Tra.count()) Dp[i]=Now;
                    Dp[i].Mst&=Now.Mst;
                }
            }
            printf("%d\n",Maxv-Dp[n].Maxs);
            for(rg int i=1;i<=q;i++) putchar(Dp[n].Tra[i]?'Y':'N');
            printf("\n%d\n",(int)Dp[n].Mst.count());
            for(rg int i=1;i<=q;i++) if(Dp[n].Mst[i]) printf("%d ",i);
            printf("(%d %d)\n",Dp[2].Maxs,(int)Dp[2].Tra.count());
        }
}TP2;
int main()
{   
    n=Read();   k=Read();
    for(rg int i=2;i<=n;i++) A[i]=Read();
    for(rg int i=n;i>=2;i--) A[i]-=A[i-1],Maxv+=A[i]*k;
    q=Read();
    for(rg int i=1;i<=q;i++)
        App[i].Le=Read(),App[i].Ri=Read();
    if(k==1)  TP2.Solve();
}

$40\%$算法

首先这是一个网络流经典模型。
应在各个站台间连容量为$k$，费用为$0$的边，然后各个区间两端连容量为$1$，费用为$dis[r]-dis[l]$的边（看作两种不同的选择）。
跑最大费用最大流即可。

跑最大费用与最小费用的区别是，$dis$数组初值置为$-inf$，然后每次把$dis$数组往上更新。
乘车的乘客就是满流的、容量减为$0$的带费用边所代表的乘客。

$60\%$算法

注意到有一种套路，如果要同时最小化或最大化两个量$a,b$，则等价于最小化或最大化$aM+b$。
但是，$M$必须大到足以区分$a,b$。一般来说，$M>max\{abs(a-b)\}$。

在当前题目中，$a$对应代价，$b$对应乘车人数。
于是把带费用边的费用改为$(dis[r]-dis[l])*M+b$即可。

$100pts$算法

针对每个乘客的区间，可以在残量网络上跑一跑最大费用最大流（即找一找有没有不走当前乘客区间的、收益相同的方案）。
若该区间内，收益仍然等于该区间带费用边的费用，就说明不一定要走一开始用的带费用边，且方案仍最优；即可不选该乘客。
反之必选。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#define re register
#define il inline
#define ll long long
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define fp(i,a,b) for(re int i=a;i<=b;i++)
#define fq(i,a,b) for(re int i=a;i>=b;i--)
using namespace std;
const int mod=1e9+7,N=8005,inf=1e9,M=1e6;
struct Edge{int to,nxt,w;ll c;}e[N*100];
struct data{int l,r;}a[N];
int n,k,h[N],cnt=1,q,S,T,pv[N],pe[N],gu[N],p[N],top,sta[N];
ll dis[N],ans;
bool vis[N];
queue<int>Q;
il void add(re int u,re int v,re int w,re ll c)
{
  e[++cnt].to=v;e[cnt].nxt=h[u];e[cnt].w=w;e[cnt].c=c;h[u]=cnt;
  e[++cnt].to=u;e[cnt].nxt=h[v];e[cnt].w=0;e[cnt].c=-c;h[v]=cnt;
}
il ll gi()
{
   re ll x=0,t=1;
   re char ch=getchar();
   while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
   if(ch=='-') t=-1,ch=getchar();
   while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
   return x*t;
}
il int SPFA(re int S)
{
  memset(dis,-63,sizeof(dis));dis[S]=0;vis[S]=1;Q.push(S);
  while(!Q.empty())
    {
      re int u=Q.front();Q.pop();
      for(re int i=h[u];i+1;i=e[i].nxt)
    {
      re int v=e[i].to;
      if(e[i].w&&dis[v]<dis[u]+e[i].c)
        {
          dis[v]=dis[u]+e[i].c;
          pe[v]=i;pv[v]=u;
          if(!vis[v]) vis[v]=1,Q.push(v);
        }
    }
      vis[u]=0;
    }
  return dis[T]>dis[0];
}
int main()
{
  freopen("reunion.in","r",stdin);
  freopen("reunion.out","w",stdout);
  memset(h,-1,sizeof(h));
  n=gi();k=gi();S=n+1;T=S+1;
  fp(i,2,n) p[i]=gi();
  q=gi();
  fp(i,1,q) a[i].l=gi(),a[i].r=gi(),add(a[i].l,a[i].r,1,(p[a[i].r]-p[a[i].l])*M+1),gu[i]=cnt-1;
  add(S,1,k,0);fp(i,1,n-1) add(i,i+1,k,0);add(n,T,k,0);
  while(SPFA(S))
    {
      re ll sum=1e18;
      for(re int i=T;i!=S;i=pv[i]) sum=min(sum,e[pe[i]].w);
      for(re int i=T;i!=S;i=pv[i]) e[pe[i]].w-=sum,e[pe[i]^1].w+=sum;
      ans+=sum*dis[T];
    }
  printf("%lld\n",p[n]*k-ans/M);
  fp(i,1,q) if(e[gu[i]].w) putchar('N');else putchar('Y');puts("");
  fp(i,1,q)
    {
      if(e[gu[i]].w) continue;
      SPFA(a[i].l);
      if(dis[a[i].r]<(p[a[i].r]-p[a[i].l])*M+1) sta[++top]=i;
    }
  printf("%d\n",top);
  fp(i,1,top) printf("%d ",sta[i]);puts("");
  fclose(stdin);
  fclose(stdout);
  return 0;
}