属于我的费用流版本终于诞生了！想来还有点小激动呢…看了下模板，之后完全按照自己的想象来写，这样在考场上也不怕啦~
某人说其实费用流就是把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=;
var head,prep:array[..maxn] of ptype;
visit:array[..maxn] of boolean;
q,dis,pre:array[..maxn] of longint;
time:array[..,..] 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:=;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:=;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),);
fillchar(pre,sizeof(pre),);
fillchar(visit,sizeof(visit),false);
fillchar(dis,sizeof(dis),$7f);
star:=;rear:=;q[star]:=st;visit[st]:=true;dis[st]:=;
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]=);
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:=;
while spfa do inc(mincost,addcost);
end; begin
//assign(input,'repair.in');reset(input);
//assign(output,'repair.out');rewrite(output);
readln(m,n);
st:=;ed:=n+n*m+;
for i:= to n do
for j:= to m do
read(time[i,j]);
for i:= to n do
insert(st,i,,,);
for i:=n+n*m downto n+ do
insert(i,ed,,,);
for i:= to n do
for j:= to m do
for k:= to n do
insert(i,j*n+k,,,(n-k+)*time[i,j]);
writeln(mincost/n::);
//close(input);close(output);
end.
repair
本题也是BZOJ 1070
啊啊啊还有2天就要坐灰机了，说来时间真的不多了。简单列一下还要复习的东西吧：树状数组/线段树，Splay(Ex.Cashier)，KMP，Tarjan相关，并查集，二分匹配相关……好像也没时间搞别的了？~TAT~