记录编号	232948	评测结果	AAAAAAAAAA
题目名称	运输问题4	最终得分	100
用户昵称	ConanQZ	是否通过	通过
代码语言	Pascal	运行时间	0.007 s
提交时间	2016-03-03 17:23:36	内存使用	0.39 MiB

    program maxfiowd;
    uses math;
    var
    pp:array[1..110]of boolean;
    c:array[1..110,1..110]of longint;
    p:array[1..110,1..110]of longint;
    from:array[1..110]of longint;
    f,i,j,n,bb,ee:longint;

    function search:boolean;
    var
    list:array[1..110]of longint;
    pay:array[1..110]of longint;
    head,tail,now:longint;
    begin
    fillchar(pp,sizeof(pp),false);
    for i:=1 to n do
    pay[i]:=maxlongint;

    head:=0;
    tail:=1;
    list[1]:=1;
    pp[1]:=true;
    pay[1]:=0;

    while head<tail do
      begin
       inc(head);
       now:=list[head];
       for i:=1 to n do
         begin
          if (c[now,i]>0)and(pay[i]>pay[now]+p[now,i]*c[now,i]) then
            begin
             pay[i]:=pay[now]+p[now,i]*c[now,i];
             from[i]:=now;
             if not pp[i] then
               begin
                inc(tail);
                list[tail]:=i;
                pp[i]:=true;
               end;
            end;
         end;
      end;
    if pp[ee] then exit(true) else exit(false);
    end;

    function dfs(now:longint):longint;
    var
    pay,ss,cc:longint;
    begin
    ss:=now;
    cc:=maxlongint;

    while ss<>bb do
      begin
       cc:=min(cc,c[from[ss],ss]);
       ss:=from[ss];
      end;
    ss:=now;
    while ss<>bb do
      begin
       dec(c[from[ss],ss],cc);
       inc(c[ss,from[ss]],cc);
       ss:=from[ss];
      end;

    pay:=0;
    while now<>bb do
      begin
       inc(pay,p[from[now],now]*cc);
       now:=from[now];
      end;
    exit(pay);
    end;

    begin
    assign(input,'maxflowd.in');
    assign(output,'maxflowd.out');
    reset(input);
    rewrite(output);
    readln(n);
    readln(bb);
    readln(ee);
    for i:=1 to n do
      begin
       for j:=1 to n do
         begin
          read(c[i,j],p[i,j]);
         end;
       readln;
      end;

    while search do
      begin
       inc(f,dfs(ee));
      end;
    writeln(f);
    close(input);
    close(output);
    end.