题解 P1315 【观光公交】

对方并不想和你说话并向你扔了一个费用流233 变量名：$tim_i$到一个点的时间 $Mx_i$一个点乘客最晚到达时间 $down_i$一个点下车人数 首先构建模型 不难发现在一个点使用加速器造成的效果是阶段性的 即在一个阶段后区间会被劈开 考虑这个劈开的条件 当前面使用的加速器超过$max(tim_i-Mx_i,0)$时就不能对后面的产生影响了 把使用加速器个数作为流量 每个点都会被分配到至多$D_i$的加速器 建立$S$、$S'$、$T$三个点 连边$S\rightarrow S'$ 容量为$K$ 费用为$0$ 起到限制总个数的作用 把所有点$i$分为$i'$和$i''$ 连边$i'\rightarrow i''$ 容量为$max(tim_i-Mx_i,0)$ 费用为$0$ 限制前面使用的加速器对后面的影响 连边$S'\rightarrow i''$ 容量为$D_i$ 费用为$0$ 分配加速器 连边$i''\rightarrow (i+1)'$ 容量为$INF$ 费用为$-down_{i+1}$ 累计费用以及传递影响 连边$i'\rightarrow T$ 容量为$INF$ 费用为$0$ 显然$1'$和$n''$是没有用的 可以在建图时舍去 然后就可以愉快的套模板了 最坏复杂度$O(k*n*log(n))$(Dijkstra)或$O(k*n^2)$(SPFA) 比贪心慢= = ```cpp #include<bits/stdc++.h> using namespace std; #define N 1010 #define M 10010 #define INF (0x3f3f3f3f) struct peo{ int t,l,r; }a[M]; struct edge{ int nxt,to,cap,cost; }e[N<<3]; int head[N<<1],edge_cnt; void add_edge(int x,int y,int z,int w){ e[edge_cnt]=(edge){head[x],y,z,w}; head[x]=edge_cnt++; e[edge_cnt]=(edge){head[y],x,0,-w}; head[y]=edge_cnt++; } int D[N],Mx[N],down[N],tim[N],S,T; struct MinCostMaxFlow{ int d[N<<1],fa[N<<1],Mn[N<<1]; bool vis[N<<1]; queue<int>Q; int calc(){ int i,res=0; while (1){ memset(d,63,sizeof(d)); d[S]=0; Q.push(S); Mn[S]=INF; while (!Q.empty()){ int x=Q.front(); Q.pop(); vis[x]=0; for (i=head[x];~i;i=e[i].nxt){ int To=e[i].to; if (!e[i].cap || d[To]<=d[x]+e[i].cost) continue; d[To]=d[x]+e[i].cost; fa[To]=i; Mn[To]=min(Mn[x],e[i].cap); if (!vis[To]){ vis[To]=1; Q.push(To); } } } if (d[T]==INF) return res; res+=Mn[T]*d[T]; int p=T; while (p!=S){ e[fa[p]].cap-=Mn[T]; e[fa[p]^1].cap+=Mn[T]; p=e[fa[p]^1].to; } } } }MCMF; int main(){ memset(head,-1,sizeof(head)); int n,m,K,i,ans=0; scanf("%d%d%d",&n,&m,&K); for (i=1;i<n;i++) scanf("%d",&D[i]); for (i=1;i<=m;i++){ scanf("%d%d%d",&a[i].t,&a[i].l,&a[i].r); down[a[i].r]++; Mx[a[i].l]=max(Mx[a[i].l],a[i].t); } for (i=1;i<n;i++) tim[i+1]=max(tim[i],Mx[i])+D[i]; for (i=1;i<=m;i++) ans+=tim[a[i].r]-a[i].t; S=n*2+1; T=n*2+3; int S1=n*2+2; add_edge(S,S1,K,0); for (i=1;i<n;i++){ add_edge(i,i+n,max(tim[i]-Mx[i],0),0); add_edge(i+n,i+1,INF,-down[i+1]); add_edge(S1,i+n,D[i],0); add_edge(i+1,T,INF,0); } printf("%d\n",ans+MCMF.calc()); return 0; } ```