题解 P1343 【地震逃生】

· · 题解

写个题解，顺便帮助自己记忆理解

var capacity:array[1..200,1..200]of longint;//记下这张网络图

flow,pre:array[1..200]of longint; //flow记录分流量，pre[i]表示某条路径中i这个节点是接在哪个点后面的

    n,m,x,a1,b1,c1,maxstream,time:longint;
    queue:array[1..100000]of longint;       //模拟栈的队列数组,c++可以不用这个,c++有专门的push和pop函数,更方便
function min(a,b:longint):longint;          //求最小值的函数
begin
     if a>b then exit(b)
     else exit(a);
end;
function bfs(src,des:longint):longint;      //搜索所有的路径,src是初始点,des是目标点
var i,j,tail,index:longint;
begin
     fillchar(queue,sizeof(queue),0);
     fillchar(pre,sizeof(pre),-1);          //填为-1表示这个点还没有它的父亲节点
     pre[src]:=0;flow[src]:=$7fffff;        //初始化pre和flow,这里将$7fffff用作正无穷
     tail:=1;queue[1]:=src;                 //将初始点入栈
     while not(tail=0)do                    //判断栈中是否有元素，没有的话说明再也找不到路径了
     begin
          index:=queue[tail];               //从栈中取出栈顶端的，也就是队列的最后一个点
          dec(tail);                        //出栈
          if(index=des)then break;          //如果这个点是目标点，说明这条路找到了，就终止循环
          for i:=1 to n do                  //遍历每个节点
          begin
               if(i<>src)and(capacity[index,i]>0)and(pre[i]=-1)then //判断当前走到的点index是否和i点相连,并且还未走过(即pre[i]=-1)
               begin
                    pre[i]:=index;                                  //记录i节点是由index点过来的
                    flow[i]:=min(capacity[index,i],flow[index]);    //取(index点的最大流)和(从index到i的最大容量)二者最小值
                    inc(tail);
                    queue[tail]:=i;                                 //将i点入栈
               end;
          end;
     end;
     if(pre[des]=-1)then exit(-1)           //如果目标点的父亲节点是-1，即找不到与目标点相连的路径
     else exit(flow[des]);                  //如果能找到路径，输出最大的分流
end;
function floyd(src,des:longint):longint;    //将所有分流遍历完统计
var increasement,sumflow,k:longint;
begin
     sumflow:=0;
     increasement:=bfs(src,des);
     while(increasement<>-1)do              //如果第一遍的搜索不能找到分流,那么这段代码就不执行，答案就是学生无法撤离
     begin                                  //如果有分流，就不断的搜索，不断的合并分流
          k:=des;                           //while里面的语句因为是套模板，这里没什么用..
          while(k<>src)do
          begin
               dec(capacity[pre[k],k],increasement);
               inc(capacity[k,pre[k]],increasement);
               k:=pre[k];
          end;
          inc(sumflow,increasement);        //合并分流
          increasement:=bfs(src,des);
     end;
     exit(sumflow);                         //得到最大网络流
end;
procedure init;
var i,j:longint;
begin
     readln(n,m,x);
     for i:=1 to m do
     begin
          readln(a1,b1,c1);
          if a1=b1 then continue;           //判断只有目标点和起始点的特殊情况
          inc(capacity[a1,b1],c1);          //考虑到2个点之间多条边的情况，所以不直接赋值
     end;
end;
begin
     init;                                  //初始化
     maxstream:=floyd(1,n);                 //遍历得到最大流
     if maxstream=0 then writeln('Orz Ni Jinan Saint Cow!')
     else                                   //最大流为0即没有路径能通过，换句话说，它的最大流量就是0
     begin
          time:=x div maxstream;            //对学生的批数进行处理输出
          if x mod maxstream<>0 then inc(time);
          writeln(maxstream,' ',time);
     end;
     readln;readln;
end.