属于我的费用流版本终于诞生了！想来还有点小激动呢…看了下模板，之后完全按照自己的想象来写，这样在考场上也不怕啦~
某人说其实费用流就是把Dinic里的BFS换成SPFA，似乎还是比较有道理的，就是addflow要做一些修改，我第一次的错误就是addflow里的循环写成了while pre[x]<>st do，正解是while x<>st do。
既然算法的问题解决了，接下来的问题就是构图的问题——如何根据题目构建对应的网络。这一题的网络非常特殊，甚至被有些OIer评论为“非主流”…我理解别人的构图也花了一些时间…主要某一个点的费用是它对之后排着的顾客的影响。例如x点表示j号员工接手的倒数第k个顾客是顾客i，那么cost[x]=(k-1)*time[i,j]，k映射成n-k就成为了我程序里的构图。在考前果断还要对各种构图熟悉一下，希望有时间。
program repair; type ptype=^node; node=record v,w,flow,cost:longint; next,op:ptype; end; const maxn=10000; var head,prep:array[0..maxn] of ptype; visit:array[0..maxn] of boolean; q,dis,pre:array[0..maxn] of longint; time:array[0..100,0..100] of longint; n,m,i,j,k,st,ed:longint; function min(a,b:longint):longint; begin if a<b then exit(a) else exit(b); end; procedure insert(u,v,w1,w2,cost:longint); var p1,p2,q:ptype; begin new(p1); p1^.v:=v;p1^.w:=w1;p1^.flow:=0;p1^.cost:=cost;p1^.next:=nil; q:=head[u]; if q=nil then head[u]:=p1 else begin q:=head[u]; head[u]:=p1; p1^.next:=q; end; new(p2); p2^.v:=u;p2^.w:=w2;p2^.flow:=0;p2^.cost:=-cost;p2^.next:=nil; q:=head[v]; if q=nil then head[v]:=p2 else begin q:=head[v]; head[v]:=p2; p2^.next:=q; end; p1^.op:=p2;p2^.op:=p1; end; function spfa:boolean; var star,rear,x:longint; y:ptype; begin fillchar(q,sizeof(q),0); fillchar(pre,sizeof(pre),0); fillchar(visit,sizeof(visit),false); fillchar(dis,sizeof(dis),$7f); star:=1;rear:=1;q[star]:=st;visit[st]:=true;dis[st]:=0; while star<=rear do begin x:=q[star]; y:=head[x]; while y<>nil do begin if (dis[y^.v]>dis[x]+y^.cost) and (y^.w>y^.flow) then begin dis[y^.v]:=dis[x]+y^.cost; pre[y^.v]:=x; prep[y^.v]:=y; if not visit[y^.v] then begin inc(rear); q[rear]:=y^.v; visit[y^.v]:=true; end; end; y:=y^.next; end; visit[x]:=false; inc(star); end; spfa:=not (dis[ed]=2139062143); end; function addcost:longint; var x,addflow:longint; y:ptype; begin x:=ed; addflow:=maxlongint; while x<>st do begin y:=prep[x]; addflow:=min(addflow,y^.w-y^.flow); x:=pre[x]; end; x:=ed; while x<>st do begin y:=prep[x]; inc(y^.flow,addflow); dec(y^.op^.flow,addflow); x:=pre[x]; end; addcost:=addflow*dis[ed]; end; function mincost:longint; begin mincost:=0; while spfa do inc(mincost,addcost); end; begin //assign(input,'repair.in');reset(input); //assign(output,'repair.out');rewrite(output); readln(m,n); st:=0;ed:=n+n*m+1; for i:=1 to n do for j:=1 to m do read(time[i,j]); for i:=1 to n do insert(st,i,1,0,0); for i:=n+n*m downto n+1 do insert(i,ed,1,0,0); for i:=1 to n do for j:=1 to m do for k:=1 to n do insert(i,j*n+k,1,0,(n-k+1)*time[i,j]); writeln(mincost/n:0:2); //close(input);close(output); end.
本题也是BZOJ 1070
啊啊啊还有2天就要坐灰机了，说来时间真的不多了。简单列一下还要复习的东西吧：树状数组/线段树，Splay(Ex.Cashier)，KMP，Tarjan相关，并查集，二分匹配相关……好像也没时间搞别的了？~TAT~