-
Notifications
You must be signed in to change notification settings - Fork 6
/
sap+gap.pas
executable file
·136 lines (121 loc) · 2.58 KB
/
sap+gap.pas
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
124
125
126
127
128
129
130
131
132
133
134
135
136
program c066;
const
ProName = 'ditch';
inf = ProName+'.in';
ouf = ProName+'.out';
maxLongword = maxlongint*2;
type
quene = object
q : array[1..200] of integer;
b,e,c : integer;
procedure add(x:integer);
function del():integer;
end;
procedure quene.add(x:integer);
begin
inc(e);
q[e]:=x;
inc(c);
end;
function quene.del():integer;
begin
inc(b);
del:=q[b];
dec(c);
end;
var
g,f : array[1..200,1..200] of int64;
m,n : integer;
l : array[1..200] of integer;
b : array[1..200] of boolean;
ans : int64;
q : quene;
function find(x:integer):boolean;
var
t:integer;
i:integer;
begin
q.e:=0;
q.c:=0;
q.b:=0;
fillchar(l,sizeof(l),0);
fillchar(b,sizeof(b),false);
l[1]:=1;
q.add(x);
while q.c > 0 do
begin
t:=q.del;
for i:= 1 to m do
if (l[i] = 0) and ((g[t,i] - f[t,i] > 0) or (f[i,t] > 0)) then
begin
l[i]:=t;
b[i]:=(g[t,i] - f[t,i] > 0);
q.add(i);
if i = m then
exit(true);
end;
end;
exit(false);
end;
procedure increase(x:integer);
var
d:int64;
i:integer;
begin
i:=x;
d:=maxlongword;
while i <> 1 do
begin
if b[i] then
begin
if g[l[i],i] - f[l[i],i] < d then
d:=g[l[i],i] - f[l[i],i]
end
else
begin
if f[i,l[i]] < d then
d:=f[i,l[i]];
end;
i:=l[i];
end;
i:=x;
while i <> 1 do
begin
if b[i] then
inc(f[l[i],i],d)
else
dec(f[i,l[i]],d);
i:=l[i];
end;
inc(ans,d);
end;
procedure readin;
var
i:byte;
b,e:byte;
w:int64;
begin
readln(n,m);
for i:=1 to n do
begin
readln(b,e,w);
inc(g[b,e],w);
end;
end;
procedure work;
var
i:integer;
begin
while find(1) do increase(m);
end;
begin
assign(input,inf);
reset(input);
assign(output,ouf);
rewrite(output);
readin;
work;
writeln(ans);
close(input);
close(output);
end.