4
9
2015
0

网络流-最大流-augment

嗯。。关于网络流问题以及augment详解，参见这里。Following: Pascal Code
 
一节毛爷爷课写的
?
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
uses
        math;
type
    {node_st=record
        p,t:longint;
    end;}
    arr_st=array[1..1000000]of longint;
var
    st:arr_st;
    R,G:array[1..1000,1..1000]of longint;
    tot,s,t,edges,best:longint;
function beside(st:arr_st;node:longint):boolean;
var
  i:longint;
begin
    for i:=1 to tot do
    begin
        if st[i]=node then exit(true);
    end;
    exit(false);
end;
 
function getmini(st:arr_st):longint;
var
    i:longint;
begin
    i:=1;
    getmini:=R[st[1]][st[2]];
    while (st[i+1]<>0)do
    begin
      getmini:=min(R[st[i]][st[i+1]],getmini);
    inc(i);
    end;
  exit(getmini);
end;
 
 
function aug(node:longint;var st:arr_st):boolean;
var
  i:longint;
  flag,geta:boolean;
begin
  if node=t then
    begin
    inc(tot);
        st[tot]:=0;
        exit(true);
    end;
  flag:=false;
    for i:=1 to edges do
    begin
        if (R[node][i]>0)and(not beside(st,i)) then
        begin
      flag:=true;
            inc(tot);
            st[tot]:=i;
            geta:=aug(i,st);
        end;
    if geta then exit(true);
    end;
  if flag=false then
    st[tot]:=0;
  dec(tot);
    if node = s then
  begin
     fillchar(st,sizeof(st),0);
     exit(false);
  end;
end;
 
procedure change(num:longint);
var
    i:longint;
begin
    i:=1;
    while (st[i+1]<>0)do
    begin
        dec(R[st[i]][st[i+1]],num);
    inc(i);
    end;
end;
procedure solve;
var
    b:boolean;
  mini:longint;
begin
    repeat
    tot:=1;
    fillchar(st,sizeof(st),0);
    st[1]:=s;
    b:=aug(s,st);
        mini:=getmini(st);
        change(mini);
    inc(best,mini);
    until not b;
end;
 
procedure init;
var
    i,cap,x,y:longint;
begin
    readln(s,t,edges);
    fillchar(R,sizeof(R),0);
    fillchar(G,sizeof(G),0);
    for i:=1 to edges do
    begin
        readln(x,y,cap);
        G[x][y]:=cap;
        inc(R[x][y],cap);
    end;
end;
 
begin
  assign(input,'ms.in');
  assign(output,'ms.out');
  reset(input);
  rewrite(output);
    init;
    solve;
    writeln(best);
  close(input);
  close(output);
end.

 

关于排版问题= =我先在windows下nodepad++写的，然后闲无聊去Lazarus调试，tab缩进勿喷。
Category: 知乎 | Tags: 网络流 | Read Count: 434
Small_feed 评论 (0)

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com