题解 P1315 【观光公交】

2017-10-18 15:10:17


对方并不想和你说话并向你扔了一个费用流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)

比贪心慢= =

#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;
}