bzoj 2324 ZJOI 营救皮卡丘 费用流
题的大概意思就是给定一个无向图，边有权值，现在你有k个人在0点，要求走到n点，且满足
1：人们可以分头行动，可以停在某一点不走了
2：当你走到x时，前x-1个点必须全部走过（不同的人走过也行，即分两路走，其中一路走过1-x-1点
，另一路可以走x点）
3：道路可以多次走，点在满足2的情况下可以多次经过
求所有人走过的总路程最短
这道题历尽挫折。。。
首先我们知道想要走到x点，一定是从前x-1个点走过来，假设我们从y走过来，y<x，那么y走到x一定走的
是可以走的最短路，既然可以走x了，那么前x-1个点一定已经走过了，所以y到x的最短路就是当图只有前x点
时的y到x的最短路，那么我们可以用floyd解决，设d[k,i,j]代表只走前K个点，I到J的最短路，那么循环时，最
外层是k，直接记录d[k,i,j]就行了，因为当循环到K时，只用前K个更新过I到J的最短路，所以I到J只会走前K个点
，这时的d[i,j]就是d[k,i,j]了
那么我们对于这道题拆点，每个点拆成Ai,Bi，添加源S，汇T
规定(a,b,c,d)为连接a到b，容量为c，费用为d的有向边
那么我们先(Ai,Bi,1,0)代表这一个点被经过一次，因为每个点有效经过只有一次，下文具体解释
然后(S，0，k,0)，代表从0开始走，一共可以走k个人
然后(Bi,T,1,0)，代表一个人最终停在点I，就相当于这个流没用了，直接流出
然后我们对于每个点I，肯定会从之前的一个点走过来，这就是开始说的floyd处理的过程了，每个J，0<=j<i连向I
(J,I,1,d[I,J,I])
那么这么建的正确性到现在还没有保证，因为题中要求每个点都要被走过，这里只是连边时费用应用了下这个性质，但是
做费用流的时候是没法保证的（就是可能有的点不会被流过），那么Ai连Bi代表这个点被流过，那么我们规定必须流这个边就行了，
也就是经常说的流量的上下界（上界就是容量），规定Ai到Bi的上下界流量都为1
那么具体怎么做，假设对于点A到B规定上界为U(p)，下界为D(own)，那么我们一定会至少流U的，所以剩下的就是D-U，我们
将这条边的流量设为D-U，可这样流量平衡等式就不满足了，也就是A点应该多流出D的，B应该多流入D的，所以添加新的源点X，
汇点Y，(A,x,D,0),(y,B,D,0),(x,y,INF,0)也就是说我们把规定必须流的从X引走然后又流到Y了，这样就行了
对于下界还有一个二分的做法，内个不会。。。
然后这道题可以不用这么麻烦，可以将Ai到Bi的边的费用设成-INF，那么因为我们是最短路找增广路的，所以一定会走这一条边，
然后就好些很多了
对于这道题，还有另一种建图的方式，也是先拆点
然后没有0这个点
加入X,Y点
(s,Y,1,0)代表从0开始走，(Y,X,K,0)代表最多走K个人，
然后拆的点(Ai,Bi,-inf,0)，(Bi,Aj,1,d[j,i,j])和上一种建图代表的一样，然后我们Y,X起的是0的作用
所以(X,Ai,1,d[i,0,i]])，然后再(Ai,T,1,0)，代表走到I不走了
但是光这样建，如果K比N小的时候只会流K个，有的点流不到（上一种方法用的下界解决的），那么这时
(S,Bi,1,0)代表从0，走的人，之后去哪儿，这样直接求就行了。
还有地方可以优化，就是floyd的时候，不用三维数组存，最外层每循环一次直接连边就行了。
附两种图的代码
/**************************************************************
Problem:
User: BLADEVIL
Language: Pascal
Result: Accepted
Time: ms
Memory: kb
****************************************************************/ //By BLADEVIL
var
n, m, k :longint;
x, y, ss, st :longint;
l :longint;
d :array[..,..] of longint;
a, b, c :longint;
pre, other, len, cost :array[..] of longint;
last :array[..] of longint;
ans :longint;
dis, father :array[..] of longint;
flag :array[..] of boolean;
que :array[..] of longint; function min(a,b:longint):longint;
begin
if a>b then min:=b else min:=a;
end; procedure connect(a,b,c,d:longint);
begin
inc(l);
pre[l]:=last[a];
last[a]:=l;
other[l]:=b;
len[l]:=c;
cost[l]:=d;
end; function spfa:boolean;
var
h, t, q, p :longint;
cur :longint; begin
filldword(dis,sizeof(dis) div ,maxlongint div );
que[]:=ss; dis[ss]:=;
h:=; t:=;
while h<>t do
begin
h:=h mod +;
cur:=que[h];
flag[cur]:=false;
q:=last[cur];
while q<> do
begin
p:=other[q];
if len[q]> then
begin
if dis[p]>dis[cur]+cost[q] then
begin
father[p]:=q;
dis[p]:=dis[cur]+cost[q];
if not flag[p] then
begin
t:=t mod +;
que[t]:=p;
flag[p]:=true;
end;
end;
end;
q:=pre[q];
end;
end;
if dis[st]=maxlongint div then exit(false) else exit(true);
end; procedure update;
var
low :longint;
cur :longint;
begin
low:=maxlongint;
cur:=st;
while cur<>ss do
begin
low:=min(low,len[father[cur]]);
cur:=other[father[cur] xor ];
end;
cur:=st;
while cur<>ss do
begin
dec(len[father[cur]],low);
inc(len[father[cur] xor ],low);
if cost[father[cur]]<>-maxlongint div then
inc(ans,low*cost[father[cur]]);
cur:=other[father[cur] xor ];
end;
end; procedure init;
var
i, j :longint;
begin
read(n,m,k);
x:=*n+; y:=x+; ss:=y+; st:=ss+;
l:=;
connect(ss,,k,); connect(,ss,,);
for i:= to n do
begin
connect(*i,*i+,,-maxlongint div );
connect(*i+,*i,,maxlongint div );
connect(*i+,st,,); connect(st,*i+,,);
end;
filldword(d,sizeof(d) div ,maxlongint div );
for i:= to n do d[i,i]:=;
for i:= to m do
begin
read(a,b,c);
if c<d[a,b] then
begin
d[a,b]:=c; d[b,a]:=c;
end;
end;
for k:= to n do
begin
for i:= to n do
for j:= to n do
d[i,j]:=min(d[i,j],d[i,k]+d[k,j]);
connect(,*k,,d[,k]); connect(*k,,,-d[,k]);
for i:= to k- do
begin
connect(*i+,*k,,d[i,k]);
connect(*k,*i+,,-d[i,k]);
end;
end;
end; procedure main;
begin
while spfa do
update;
writeln(ans);
end; begin
init;
main;
end.
/**************************************************************
Problem:
User: BLADEVIL
Language: Pascal
Result: Accepted
Time: ms
Memory: kb
****************************************************************/ //By BLADEVIL
var
n, m, k :longint;
x, y, ss, st :longint;
l :longint;
d :array[..,..] of longint;
a, b, c :longint;
pre, other, len, cost :array[..] of longint;
last :array[..] of longint;
ans :longint;
dis, father :array[..] of longint;
flag :array[..] of boolean;
que :array[..] of longint; function min(a,b:longint):longint;
begin
if a>b then min:=b else min:=a;
end; procedure connect(a,b,c,d:longint);
begin
inc(l);
pre[l]:=last[a];
last[a]:=l;
other[l]:=b;
len[l]:=c;
cost[l]:=d;
end; function spfa:boolean;
var
h, t, q, p :longint;
cur :longint; begin
filldword(dis,sizeof(dis) div ,maxlongint div );
que[]:=ss; dis[ss]:=;
h:=; t:=;
while h<>t do
begin
h:=h mod +;
cur:=que[h];
flag[cur]:=false;
q:=last[cur];
while q<> do
begin
p:=other[q];
if len[q]> then
begin
if dis[p]>dis[cur]+cost[q] then
begin
father[p]:=q;
dis[p]:=dis[cur]+cost[q];
if not flag[p] then
begin
t:=t mod +;
que[t]:=p;
flag[p]:=true;
end;
end;
end;
q:=pre[q];
end;
end;
if dis[st]=maxlongint div then exit(false) else exit(true);
end; procedure update;
var
low :longint;
cur :longint;
begin
low:=maxlongint;
cur:=st;
while cur<>ss do
begin
low:=min(low,len[father[cur]]);
cur:=other[father[cur] xor ];
end;
cur:=st;
while cur<>ss do
begin
dec(len[father[cur]],low);
inc(len[father[cur] xor ],low);
inc(ans,low*cost[father[cur]]);
cur:=other[father[cur] xor ];
end;
end; procedure init;
var
i, j :longint;
begin
read(n,m,k);
x:=*n+; y:=x+; ss:=y+; st:=ss+;
l:=;
for i:= to n do
begin
connect(i,i+n,,); connect(i+n,i,,);
connect(i+n,y,,); connect(y,i+n,,);
connect(ss,i+n,,); connect(i+n,ss,,);
connect(i,st,,); connect(st,i,,);
end;
connect(y,x,k,); connect(x,y,,);
filldword(d,sizeof(d) div ,maxlongint div );
for i:= to n do d[i,i]:=;
for i:= to m do
begin
read(a,b,c);
if c<d[a,b] then
begin
d[a,b]:=c; d[b,a]:=c;
end;
end;
for k:= to n do
begin
for i:= to n do
for j:= to n do
d[i,j]:=min(d[i,j],d[i,k]+d[k,j]);
connect(x,k,,d[,k]); connect(k,x,,-d[,k]);
for i:= to k- do
begin
connect(i+n,k,,d[i,k]);
connect(k,i+n,,-d[i,k]);
end;
end;
end; procedure main;
begin
while spfa do
update;
writeln(ans);
end; begin
init;
main;
end.
最新文章
- jQuery学习之路（8）- 表单验证插件-Validation
- No package mysql-server available.
- 【亚瑟士 ASICS 系列】
- Raft一致性协议
- 简单解析依赖注入（控制反转）在Spring中的应用
- bzoj4038: 医疗援助
- Net中的反射使用入门
- 颜色rgb
- 教你如何利用初级C#语言更改银行存款!!!!
- PDF417码
- win 开机 Microsoft corparation 滚动栏
- bin home
- Yii中CDbCriteria常用总结
- Excel 2010高级应用-折线图（二）
- web过滤器
- 剑指Offer 43. 左旋转字符串 （字符串）
- 无向图最小割Stoer-Wagner算法学习
- hbase与hive集成：hive读取hbase中数据
- [转]Linux常用命令大全
- warning C4305:“初始化”:从“double”到“float”截断