图论网络流agent解题报告

1、Agent 解题沙郡中学高 992 班湖南【问题描述】Agent.doc【算法分析】这是一道典型的图论问题，首先可以根据问题给定的条件，建立起一个网络模型另一方面，因为只要Cost: Extended;弧的代价Arc,这条弧的所对应的一条前向弧或后向弧 Next: TLink;end;TPath = object每次求得的增广轨f, 该节点在增广轨上的前驱节点Min:eger;表示从初始节点到该节点的增广轨能够扩充的最大流量d: Extended;从初始节点到该节点的增广路径的总代价Po end;er: TLink;指向该节点与其在增广轨上的前驱节点之间的有向弧varG: array 1 Pa

2、th: array n, k, s, t:. 1MaxNode of TLink;邻接表. MaxNode of TPath; eger;procedure CreateGraph(const x, y, Arc :建立每一条有向弧 varp, q: TLink; begineger; Factor : Extended);New(p); p.c :=q.c := p.Next q.Nextend;New(q);Arc; p.f := Arc; p.n := y; p.Cost := - Factor;Arc; q.f := 0; q.n := x;q.Cost:=Factor;:= Gx;

3、Gx:= Gy; Gy:= p; p.Arc:= q; q.Arc:=:=q;p;procedure varInit;输出i, s1, x, y, Flow:eger;Temp, Factor: Extended;c: array 1 . MaxN of Extended; beginAssign(Input, InputFileName); Reset(Input);Readln(n, k);s := n + 1; 源点s1 := n + 2; 辅助节点t := n + for i := for i := begin3;汇点1 to n do Read(ci); 1 to n doRead(

4、x);if x 0 then CreateGraph(s1, i, x, ln(ci); end;Temp := ln(1); CreateGraph(s, s1, k, Temp); for i := 1 to n dobeginRead(x);if x 0 then CreateGraph(i, t, k, end;Read(x, y);while not (x = -1) and (y = -1) do beginReadln(Factor, Flow); Factor := ln(Factor);CreateGraph(x, y, Flow, Factor); CreateGraph(

5、y, x, Flow, Factor); Read(x, y);end;Close(Input); Inc(n, 3); end;Temp);procedure Main; varMore: i, x, Temp:;Setup:eger; Extended;p: TLink; beginrepeatfor i := 1 to n do初始化 path 数组 with Pathi dobegin := Max; d := Max; Poer:= nil;end;Paths.d := 0;repeat求解目前代价最小的增广轨 More := True;for i := 1 to n doif Pa

6、thi.d Max then beginp := Gi;while p nil do beginif p.f 0 then beginTemp := Pathi.d + p.Cost; x := p.n;if Pathx.d Temp + limit then beginMore := False; Pathx.d := Temp;Pathx.f := i;Pathx.Min := Pathi.Min;if p.f Pathx.Mhen Pathx.Min:=p.f;Pathx.Po end;end;p := p.Next; end;end; until More;Setup := Patht

7、.Min;er := p;if Setup = Max then Break;不存在可增广轨 x := t;while x s do修改增广轨上弧的流量 beginp := Pathx.Poer;p.f := p.f - Setup; p.Arc.f := p.Arc.f + Setup; x := Pathx.f;end; until False;end;procedure vari, j: Answer,Show;输出eger;Temp: Extended;p: TLink; beginAnswer := 1;for i := 1 to n do计算总的安全系数 beginp := Gi;while p nil do beginif p.Cost 0 then beginTemp := Exp(- p.Cost * (p.c - Answer := Answer * Temp;end;p := p.Next; end;end;Assign(Output, OutputFileName); Rewrite(Output);i := 0;while Answer 10000 dop.f);begin Answer := Answer * 10; Inc(i)