这道题还是比较简单的费用流,由于w是递增的

实际上,这题数据还可以强一点,比如说分段函数不保证费用递增,

就要加一点技巧了(要保证函数的顺序)

 const inf=;
type node=record
       next,point,flow,cost:longint;
     end;
var q:array[..] of longint;
    edge:array[..] of node;
    v:array[..] of boolean;
    p,time,c,d,pre:array[..] of longint;
    len,i,j,n,m,t,total,s,w,x:longint;
    ans:int64; procedure add(x,y,f,w:longint);
  begin
    inc(len);
    edge[len].point:=y;
    edge[len].flow:=f;
    edge[len].cost:=w;
    edge[len].next:=p[x];
    p[x]:=len;
  end; function spfa:boolean;
  var i,j,f,r,x,y:longint;
  begin
    fillchar(v,sizeof(v),false);
    v[]:=true;
    for i:= to t do
      d[i]:=inf;
    d[]:=;
    f:=;
    r:=;
    q[]:=;
    while f<=r do
    begin
      x:=q[f];
      v[x]:=false;
      i:=p[x];
      while i<>- do
      begin
        y:=edge[i].point;
        if edge[i].flow> then
          if d[y]>d[x]+edge[i].cost then
          begin
            d[y]:=d[x]+edge[i].cost;
            pre[y]:=i;
            time[y]:=x;
            if not v[y] then
            begin
              v[y]:=true;
              inc(r);
              q[r]:=y;
            end;
          end;
        i:=edge[i].next;
      end;
      inc(f);
    end;
    if d[t]=inf then exit(false) else exit(true);
  end; procedure mincost;
  var i,j,x,y,neck:longint;
  begin
    while spfa do
    begin
      neck:=inf;
      i:=t;
      while i<> do
      begin
        j:=pre[i];
        if neck>edge[j].flow then neck:=edge[j].flow;
        i:=time[i];
      end;
      i:=t;
      while i<> do
      begin
        j:=pre[i];
        dec(edge[j].flow,neck);
        inc(edge[j xor ].flow,neck);
        i:=time[i];
      end;
      ans:=ans+neck*d[t];
    end;
  end; begin
  readln(n,m);
  len:=-;
  fillchar(p,sizeof(p),);
  for i:= to m do
  begin
    read(c[i]);
    add(,i,c[i],);
    add(i,,,);
  end;
  for i:= to n do
  begin
    for j:= to m do
    begin
      read(x);
      if x= then
      begin
        add(j,i+m,c[j],);
        add(i+m,j,,);
      end;
    end;
  end;
  t:=n+m+;
  for i:= to n do
  begin
    readln(s);
    fillchar(time,sizeof(time),);
    for j:= to s do
      read(time[j]);
    for j:= to s do
    begin
      read(w);
      add(i+m,t,time[j]-time[j-],w);
      add(t,i+m,,-w);
    end;
    read(w);
    add(i+m,t,inf,w);
    add(t,i+m,,-w);
  end;
  mincost;
  writeln(ans);
end.
04-20 18:55