Basic algorithm

a [i, j]: = a [i, k] a [k, j];

P [I, J]: = P [k, j];

END;

END;

C. Dijkstra algorithm:

VAR

A: array [1..maxn, 1..maxn] of integer;

B, pre: array [1..maxn] of integer; {pre [i] refers to the front disseval point of i on the shortest path.

Mark: array [1..maxn] of boolean;

Procedure Dijkstra (V0: Integer);

Begin

Fillchar (Mark, Sizeof (Mark),

FALSE);

For i: = 1 to n

Do Begin

D [i]: = a [v0, i];

IF D [i] <> 0

Then pre [I]: = V0

Else pre [I]: = 0;

END;

Mark [V0]: =

True;

Repeat {Add a nearest node close to 1 episodes per loop and adjust the parameters of other nodes}

MIN: = Maxint; u: = 0; {u Record from 1 episode nearest node}

For i: = 1 to n

DO

IF (Not Mark [i]) and (d [i]

Then Begin

u: = i; min: = d [i];

END;

IF u <> 0

Then Begin

Mark [u]: =

True;

For i: = 1 to n

DO

IF (Not Mark [I]) and (a [u, i] d [u]

Then Begin

D [i]: = a [u, i] d [u];

Pre [i]: = u;

END;

END;

Until u = 0;

END;

3. Calculate the pass closure

PROCEDURE longlink;

VAR

T: array [1..maxn, 1..maxn] of boolean;

Begin

Fillchar (T, Sizeof (T),

FALSE);

Fork: = 1 to n

DO

For i: = 1 to n

DO

For j: = 1 to n

DO T [I, J]: = T [i, j] or (t [i, k] and t [k, j]);

END;

4. Non-map connected component

A. Depth priority

Procedure DFS (Now, Color: Integer);

Begin

For i: = 1 to n

DO

IF a [now, i] and c [i] = 0

Then Begin {dye to node i}

C [I]: = Color;

DFS (I, Color);

END;

END;

B width priority (seed staining)

5. Critical Path

Several definitions: The vertex 1 is the source point, n is a combo.

a. Top events earliest time VE [J], VE [J] = Max {VE [J] W [i, j]}, where VE (1) = 0;

b. Top events Time VL [J], VL [J] = min {VL [J] - W [i, J]}, where VL (n) = VE (N);

c. The earliest start time of the event EE [i], if the side i is represented by , then EE [i] = ve [j];

d. The last time EL [i] is starting at the end of the event, if the side i is indicated by , EL [i] = VL [K] - W [J, K]; if EE [J] = EL [ j], the activity j is a critical activity, and the path consists of key activities is a critical path.

Solution:

a. From the source point to TOPSORT, determine if there is loop and calculate the VE;

b. From the exchange points to Tops, seeking VL;

EE and EL;

6. Topology sort

The point of finding 0 is 0, and the other side of which is connected is deleted, and the process is repeated.

For example, the sum of any continuous P items is positive, any Q item and the negative, if there is no existence, output NO.

7. Logging problem

Euler loop (DFS)

Definition: Only one loop through each side of the figure. (Mon for conditions: Figure is connected with and not quenching)

Hamilton loop

Definition: The loop is only once through each vertex.

A brush

MA. Active condition: Figure Tong Tong and the number of odds are 0 or 2.

9. Is there a negative circuit Bellman-Ford algorithm in the figure?

X [i], y [i], t [i] indicates the starting point, end point, and weight of the first edge of the clip. A total of n nodes and M strips.

Procedure Bellman-ford

Begin

For i: = 0 to n-1

Do D [I]: = Infinitive;

D [0]: = 0;

For i: = 1 to n-1

DO

For j: = 1 to m

Do {enumeration every side}

IF D [X [J]] T [J]

THEN D [Y [J]]: = D [x [J]] T [J];

For i: = 1 to m

DO

IF D [X [J]] T [J]

Then Return

False

Else Return

True;

END;

10. Nth shortest path problem

* Second shortest path: Each side of the shortest path, each delete one, then ask the shortest path to the new map, take the shortest one of these paths to the second shortest path.

* Similarly, the Nth shortest path can be solved on the basis of solving the N-1 shortest path.

Third, backpack problem

* Some backpack problems can have greedy solution: calculate PI / Wi

data structure:

w [i]: the weight of the i-th backpack;

p [i]: The value of the i-th backpack;

1.0-1 Backpack: Each backpack can only use once or limited (convertible to once):

A. Ask for maximum weight.

NOIP2001 packing problem

There is a box capacity of V (positive integer, o ≤ V ≤ 20000), and N items (O ≤ N ≤ 30), each item has a volume (positive integer). Requires from N items, if you have a thousand loading boxes, the remaining space of the box is minimized.

l search method

Procedure Search (K, V: Integer); {Searching the kth item, the remaining space is V}

Var i, J: integer;

Begin

IF v

THEN BEST: = V;

IF v- (s [n] -s [k-1])> = best

THEN EXIT; {s [n] is the weight and} of the previous N items.

IF k <= n

Then Begin

IF v> w [k]

THEN Search (k 1, v-w [k]);

Search (k 1, v);

END;

END;

l dp

F [i, j] Select several pieces of the previous I to put it in a marker that is just J J. is a Boolean.

Implementation: Transformation of optimized problems into judgment issues

F [i, j] = f [i-1, j-w [i]] (w [i] <= j <= v) boundary: f [0 ,0]: = true.

For i: = 1 to n

DO

For j: = w [i] to v

Do F [i, j]: = f [i-1, j-w [i]];

Optimization: The current state is only related to the previous stage state, which can be reduced to one dimension.

F [0]: =

True;

For i: = 1 to n

Do Begin

F1: = f;

For j: = w [i] to v

DO

IF F [J-W [i]]]

THEN F1 [J]: =

True;

F: = f1;

END;

B. The maximum value that can be placed.

F [i, j] is the maximum value that the previous J backpack can obtain for the capacity of i.

F [i, j] = max {f [i - w [j], j-1] p [j], f [i, j-1]}

C. Ask the number of applications that is full.

DP:

Procedure Update;

Var J, K: Integer;

Begin

C: = a;

For j: = 0 to n

DO

IF a [j]> 0

THEN

IF J now <= n

THEN INC (C [J Now], A [J]);

A: = C;

END;

2. Repeatable backpack

A seeking up to the weight can be placed.

F [i, j] Select several pieces of the previous I to put it in a marker that is just J J. is a Boolean.

The state transfer equation is

F [i, j] = f [i-1, j - w [i] * k] (k = 1 .. J DIV W [i])

B. The maximum value that can be placed.

USACO 1.2 Score Inflation

Take a competition, the total time T is fixed, there are several optional questions, each of the topics can be selected, each topic has a Ti (answer the time required to answer this question) and a Si (answer this question) The resulting score), now choose a number of questions, the total number of points obtained by the total time of these questions, the maximum score obtained, and the maximum score.

* It is easy to think:

F [i, j] = max {f [i-k * w [j], j-1] k * p [j]} (0 <= k <= I DIV W [J])

Where F [I, J] indicates that the maximum value that the front J table backpack can achieve when the capacity is i.

*achieve:

Begin

Fillchar (f, sizeof (f), 0);

For i: = 1 to m

DO

For j: = 1 to n

DO

IF i-quobem [j] .time> = 0

THEN

Begin

T: = problem [j] .point f [i-quobem [j] .time];

IF T> f [i]

THEN F [I]: = T;

END;

Writeln (f [m]);

End.

C. Ask the number of applications that is full.

Ahoi2001 Problem2

Seeking natural number n Number of nature and the number of expressions.

Idea, generate the arrangement of the coefficients of each rigidity, test in one by one, this is a form of a law.

Procedure

TRY (dep: integer);

Var i, J: integer;

Begin

Cal; {This process calculates the calculation result of the current coefficient, the result is the result}

IF now> n

{Twilight}

IF DEP = L 1

Then Begin generates all coefficient}

Cal;

IF now = n

THEN INC (TOT);

EXIT;

End; for i: = 0 to n Div PR [DEP]

Do Begin

XS [dep]: = i;

TRY (DEP 1);

XS [dep]: = 0;

END;

END;

Idea II, recursive search efficiency is high

Procedure

TRY (DEP, REST: INTEGER);

Var i, j, x: integer;

Begin

IF (REST <= 0) OR (DEP = L 1)

Then Begin

IF rest = 0

THEN INC (TOT);

EXIT;

END;

For i: = 0 TO REST DIV PR [DEP]

DO

TRY (DEP 1, REST-PR [DEP] * i);

END;

{main:

Try (1, n);}

Ideas 3: Can be solved using dynamic planning

USACo1.2 Money

SYSTEM

V Item, the backpack capacity is n, and the total number of flasks is found.

Transfer equation:

Procedure Update;

Var J, K: Integer;

Begin

C: = a;

For j: = 0 to n

DO

IF a [j]> 0

THEN

Fork: = 1 to n Div Now

DO

IF J Now * K <= n

THEN INC (C [J Now * K], A [J]);

A: = C;

END;

{main}

Begin

Read (now); {Reading the weight of the first item}

I: = 0; {a [i] is the total number of} when the backpack capacity is i}

While i <= n

Do Begin

a [i]: = 1; INC (i, now);

End; {Define the weight a value of the weight of the first item is 1, as a primary value}

For i: = 2 to v

DO

Begin

Read (now);

Update; {Dynamic Update}

END;

Writeln (a [n]);

Fourth, ordering algorithm

1. Quick sort:

Procedure Qsort (L, R: Integer);

Var i, j,

MID: Integer;

Begin

I: = L; J: = R;

MID: = a [(1 r) Div 2]; {Define the number of the current sequence in the middle position as an intermediate number}

Repeat

While a [i] <

MID

Do INC (i); {in the left half is looking for a large number of middle numbers

While a [J]>

MID

Do Dec (j); {{在 半 半 小 小 number}

IF i <= j

The begin {If you find a group of casters that are inconsistent with the sorting target, exchange them}

SWAP (a [i], a [j]);

INC (i); dec (j); {continuing to find}

END;

Until I> J;

IF L

Then Qsort (L, J); {If there is no boundary of the two numbers, recursive search left and right intervals}

IF i

THEN QSORT (i, r);

End; {sort}

B. Insert Sort:

Idea: Current a [1] .. a [i-1] has been ranked, now inserting a [i] to make A [1] .. a [i] is orderly.

Procedure insert_sort;

Var i, J: integer;

Begin

For i: = 2 to n

Do Begin

a [0]: = a [i];

J: = I-1;

a [j 1]: = a [j];

J: = J-1;

END;

a [j 1]: = a [0];

END;

End; {INSET_SORT}

C. Select Sort:

Procedure sort;

Var i, J, K: Integer; Begin

For i: = 1 to n-1

DO

For j: = i 1 to n

DO

IF a [i]> a [j]

THEN SWAP (a [i], a [j]);

END;

D. Sprinkle

Procedure bubble_sort;

Var i, j, k: integer;

Begin

For i: = 1 to n-1

DO

For J: = N DOWNTO I 1

DO

END;

E. Stack Sort:

Procedure Sift (I, M: Integer); {Adjusting the subtree of I root into a pile, M is the total number of nodes}

VAR K: Integer;

Begin

a [0]: = a [i]; k: = 2 * i; {The left child of the node i in the full binary tree is 2 * i, the right child is 2 * i 1}

While K <= m

Do Begin

IF (k

THEN INC (K); {finds a larger value in A [K] and A [K 1]}

end

ELSE K: = M 1;

END;

a [i]: = a [0]; {Put the root in the right position}

END;

Procedure Heapsort;

VAR

J: integer;

Begin

For J: = N DIV 2 Downto 1

DO SIFT (J, N);

For j: = n Downto 2

Do Begin

SWAP (A [1], A [J]);

SIFT (1, j-1);

END;

END;

F. Multiplexing

{A is a sequence list, TMP is auxiliary array}

Procedure Merge (VAR A: LISTTYPE; P, Q, R: Integer);

{Mr. A [p..Q] and A [Q 1..r]} of the sorted subsequences and A [Q 1..r]}

Var i, j, t: integer;

TMP: LISTTYPE;

Begin

T: = p; i: = p; j: = q 1; {t is TMP pointer, i, j is a pointer of left and right subsequences, respectively.

While (t <= r)

Do Begin

IF (i <= q) {left sequence has the remaining} and ((j> R) OR (a [i] <= a [j])) {Meet the requirements of the current element of the left sequence}

Then Begin

TMP [T]: = a [i]; INC (i);

end

Else Begin

TMP [T]: = a [j]; inc (j);

END;

INC;

END;

For i: = p to r

Do A [I]: = TMP [i];

End; {merge}

Procedure merge_sort (var A: listType; p, r: integer); {merge sorting a [p..r]}

Var q: integer;

Begin

IF P <> r

Then Begin

Q: = (p r-1) DIV 2;

Merge_sort (A, P, Q);

MERGE_SORT (A, Q 1, R);

MERGE (A, P, Q, R);

END;

END;

{main}

Begin

Merge_sort (a, 1, n);

End.

G. Boundary Sort

Thought: For each element, you can sort each bit from low to high.

V. High precision calculation

Definition of high precision:

Type

HP = array [1..maxlen] of integer;

1. High-precision addition Procedure Plus (a, b: hp; var C: HP);

Var i,

Len: integer;

Begin

Fillchar (C, SizeOf (C), 0);

IF a [0]> b [0]

THEN

Len: = a [0]

Else

LEN: = B [0];

For i: = 1 to

Len

Do Begin

INC (C [I], A [I] B [I]);

IF C [I]> 10

The begin dec (C [I], 10); INC (C [i 1]);

End; {carry}

END;

IF C [

Len 1]> 0

THEN INC

Len;

C [0]: =

Len;

End; {plus}

2. High precision subtraction

Procedure Substract (A, B: HP; VAR C: HP);

Var i,

Len: integer;

Begin

Fillchar (C, SizeOf (C), 0);

IF a [0]> b [0]

THEN

Len: = a [0]

Else

LEN: = B [0];

For i: = 1 to

Len

Do Begin

INC (C [I], A [I] -B [I]);

IF C [i] <0

THEN Begin Inc (C [I], 10); DEC (C [i 1]);

END;

WHILE

Len> 1) and (c [

Len] = 0)

Do Dec (

Len;

C [0]: =

Len;

END;

3. High precision multiplied by low accuracy

Procedure Multiply (a: hp; b: longint; var C: HP);

Var i,

Len: integer;

Begin

Fillchar (C, SizeOf (C), 0);

Len: = a [0];

For i: = 1 to

Len

Do Begin

INC (C [I], A [I] * b);

INC (C [i 1], (a [i] * b) DIV 10);

C [i]: = C [i] mod 10;

END;

Inc

Len;

While (C "

LEN]> = 10)

Do Begin {Treat the highest position}

Chan

Len 1]: = C [

Len] DIV 10;

Chan

Len]: = C [

Len] MOD 10;

Inc

Len;

END;

WHILE

Len> 1) and (c [

Len] = 0)

Do Dec (

Len); {If you don't need to carry it, adjust

Len}

C [0]: =

Len;

End; {Multiply}

4. High precision multiplied by high precision

Procedure high_multiply (a, b: hp; var c: hp}

Var i, j,

Len: integer;

Begin

Fillchar (C, SizeOf (C), 0);

For i: = 1 to a [0]

DO

For j: = 1 to b [0]

Do Begin

INC (C [i J-1], A [I] * B [J]);

INC (C [i J], C [i J-1] DIV 10);

C [i j-1]: = C [i j-1] mod 10;

END;

Len: = a [0] b [0] 1;

WHILE

Len> 1) and (c [

Len] = 0)

Do Dec (

Len;

C [0]: =

Len;

END;

5. High precision dividend

Procedure devide (a: hp; b: longint; var c: hp; var d: longint);

{C: = a div b; d: = a mod b} var i,

Len: integer;

Begin

Fillchar (C, SizeOf (C), 0);

LEN: = a [0]; D: = 0;

For i: =

Len Downto 1

Do Begin

D: = D * 10 a [i];

C [I]: = D DIV B;

D: = D mod b;

END;

WHILE

Len> 1) and (c [

Len] = 0)

THEN DEC

Len;

C [0]: =

Len;

END;

6. High precision divide high precision

Procedure high_devide (A, B: HP; VAR C, D: HP);

VAR

i,

Len: integer;

Begin

Fillchar (C, SizeOf (C), 0);

Fillchar (D, SizeOf (D), 0);

LEN: = a [0]; d [0]: = 1;

For i: =

Len Downto 1

Do Begin

Multiply (d, 10, d);

D [1]: = a [i];

While (Compare (d, b)> = 0)

DO {即 D> = B}

Begin

Subtract (d, b, d);

INC (C [I]);

END;

END;

WHILE

Len> 1) and (c.s [

Len] = 0)

Do Dec (

Len;

C.

Len: =

Len;

END;

Sixth, the traversal of the tree

1. Required sequence in pre-sequence

Procedure Solve (Pre,

MID: String);

VAR i: integer;

Begin

IF (pre = '') or

MID = '')

.

I: = POS (pre [1],

MID);

Solve (Copy (Pre, 2, i), COPY

MID, 1, I-1));

Solve (Pre, i 1, Length (Pre) -i), COPY (

MID, I 1, Length (

MID) -i));

Post: = post pre [1]; {plus root, post-recursive end traversal traversal}

END;

2. Present sequence prequet sequence

Procedure SOLVE

MID, POST: STRING;

VAR i: integer;

Begin

IF

MID = '') or (post = '')

.

I: = POS (post [length (post)],

MID);

Pre: = pre post [length (post)]; {plus root, after recursive end, pre-sequence traversal}

Solve (Copy)

MID, 1, I-1), COPY (POST, 1, I-1);

Solve (Copy)

MID, I 1, Length (

MID) -i), Copy (Post, I, Length (post) -i);

END;

3. One of known pre-sequences

Function OK (S1, S2: String): Boolean;

Var i, l: integer; p: boolean;

Begin

OK: =

True;

L: = Length (S1);

For i: = 1 to L

Do Begin

P: =

False;

For j: = 1 to L

DO

IF S1 [I] = S2 [J]

THEN P: =

True;

IF not p

Then Begin OK: =

False; exit;

END;

END;

Procedure Solve (Pre, Post: String);

VAR i: integer;

Begin

IF (pre = '') or (post = '')

.

I: = 0;

Repeat

INC (I);

Until OK (Copy (Pre, 2, I), Copy (POST, 1, I));

Solve (Copy (Pre, 2, I), COPY (POST, 1, I));

Midstr: = Midstr pre [1];

Solve (Copy (Pre, I 2, Length (Pre) -i-1), Copy (POST, I 1, Length (POST) -i-1);

END;

Seven-based conversion

1 Mutualization of any positive integer

In addition to N

2 Real numbers arbitrarily interacting

Take N

3 negative numbers:

Design a program, read into a decimal number of bases and a base of the load, and convert this decimal number to this load: -r∈ {-2, -3, -4, .. ..- 20}

Eight all arrangement and combination

1 Arranged: (1..n)

Procedure Solve (dep: integer);

VAR

i: integer;

Begin

IF dep = N 1

The begin Writeln (S); EXIT;

END;

For i: = 1 to n

DO

IF NOT USED [I]

Then Begin

S: = S CHR (i ORD ('0')); used [i]: =

True;

Solve (dep 1);

S: = COPY (S, 1, Length (s) -1); used [i]: =

False;

END;

END;

2 Combination generation (all options for selecting K numbers in 1..n)

Procedure Solve (dep, pre: integer);

VAR

i: integer;

Begin

IF dep = K 1

The begin Writeln (S); EXIT;

END;

For i: = 1 to n

DO

IF (not used [i]) and (i> pre)

Then Begin

S: = S CHR (i ORD ('0')); used [i]: =

True;

Solve (DEP 1, I);

S: = COPY (S, 1, Length (s) -1); used [i]: =

False;

END;

END;

IX. Find algorithms

1% off

Function Binsearch (K: KeyType): Integer;

Var low, HIG,

MID: Integer;

Begin

Low: = 1; HIG: = N;

MID: = (low HIG) DIV 2;

While (a [A [

MID]. Key <> k) and (low <= HIG)

Do Begin

IF a [

MID] .Key> K

Then Hig: =

MID-1

Else Low: =

MID 1;

MID: = (low HIG) DIV 2;

END;

IF low> HIG

THEN

MID: = 0;

BINSEARCH: =

MID;

END;

2 tree look

Binary Sort Tree: The value of each node is greater than the value of its left sub-tree, which is less than the value of its right tree.

Look up

Function Treesrh (K: KeyType): Pointer;

VAR Q: POINTER;

Begin

Q: = root; while (q <> nil) and (q ^ .key <> K)

DO

IF K

= q ^.

Left

ELSE Q: = Q ^.

Right;

Treesrh: = q;

END;

Ten, greedy

* Meeting questions

(1) N An event has a start time and an end time, only one event is only in one activity, and the maximum number of activities is satisfied.

Solution: Sort by the end time of each activity, the top priority is satisfied.

(2) The meeting room has the least free time.

(3) Every customer has a wish to pay for maximum profit.

(4) Conference rooms in total R, iile I need to use I meeting rooms, the cost is the same, and ask for maximum profit.

Eleven, backtracking framework

1. N Queens

Procedure

TRY (i: byte);

Var J: byte;

Begin

IF i = n 1

.

END;

For j: = 1 to n

DO

IF a [i] and b [j i] and c [j-i]

Then Begin

x [i]: = j;

a [j]: =

False; b [j i]: =

False; C [J-I]: =

False;

TRY (i 1);

a [j]: =

True; b [i j]: =

True; C [J-I]: =

True;

END;

END;

2.Hanoi Tower H (n) = 2 * h (N-1) 1 h (1) = 1

Initial all copper sheets are on a column

Procedure Hanoi (N, A, B, C: Byte); {Move the nth-block copper sheet from the A column to the C column}

Begin

IF n = 0

.

Hanoi (N-1, A, C, B); {Move the above N-1 block from the A column to the B column}

Write (N, 'Moved from', A, 'To', C);

Hanoi (N-1, B, A, C); {Move the N-1 block on B from the B column to the C column

END;

The initial copper sheet is distributed on 3 columns, given the target column Goal

H [1..3, 0..n] stores three columns, NOW and NOWP's column number and number, h [i, 0] in the nowp of the NOWP. number.

Procedure Move (k, goal: integer; {Move the greatest in position to the target column Goal}

Begin

IF k = 0

.

For i: = 1 to 3

DO

For j: = 1 to han [i, 0]

DO

IF h [i, j] = k

THEN BEGIN NOW: = I; NOWP: = J;

End; {find K position}

IF now <> Goal

Then Begin {is not moved to the target}

Move (K-1, 6-now-goal); {The remaining movement to the unused column}

Writeln (K Moved from Now To Goal);

H [Goal, H [Goal, 0] 1]: = h [now, NOWP]; H [now, nowP]: = 0;

INC (H [Goal, 0]); DEC (H [now, 0]);

Move (k-1, goal); {Left movement to the target}

END;

Twelve, DFS framework

Division of NOIP2001

Procedure Work (dep, pre, s: longint); {The entrance is Work (1, 1, n)}

{DEP is the number of number DPs of the current test, PRE is the number of previous test places, S is the total number of current remaining can be divided.

Var J: longint;

Begin

IF dep = N

Then Begin

IF s> = pre

Then incitation;

END;

For J: = pre To S Div 2

Do Work (DEP 1, J, S-J);

END;

similar:

Procedure

TRY (dep: integer);

VAR i: integer;

Begin

IF dep = K

Then Begin

if Tot> = a [DEP-1]

THEN INC (SUM);

EXIT;

END;

For i: = a [DEP-1] to Tot Div 2

Do Begin

a [dep]: = i; dec (TOT, I);

TRY (DEP 1);

INC (TOT, I);

END;

End; {

Try}

Thirteen, BFS framework

IOI94 room problem

HEAD: = 1; tail: = 0;

While Tail

Do Begin

INC; TAIL

Fork: = 1 to n

DO

IF K direction scalable

Then Begin

INC; HEAD;

List [head] .x: = list [tail] .x DX [k]; {expand new node list [head]}

List [head] .y: = list [tail] .y dy [k];

Handling new nodes list [head];

END;

END;

Fifteen, data structure related algorithm

1. Link list positioning function LOC (i: integer): Pointer; {look for pointers in the i-th sideworth in the list}

Procedure Loc (L: Linklist; i: integer): Pointer;

VAR P: ​​POINTER;

J: integer;

Begin

P: = L.HEAD; J: = 0;

IF (i> = 1) and (i <= L.

Len

THEN

While J

Do Begin P: = P ^.

NEXT; INC (j);

END;

Loc: = P;

END;

2. Single-link table insertion operation

Procedure INSERT (L: Linklist; i: integer; x: datatype);

VAR P, Q: POINTER;

Begin

P: = LOC (L, I);

NEW (q);

Q ^.

Data: = x;

Q ^.

Next: = p ^.

NEXT;

P ^.

Next: = q;

INC (L.

Len;

END;

3. Single-link table deletion

Procedure delete (l: linklist; i: integer);

VAR P, Q: POINTER;

Begin

P: = LOC (L, I-1);

Q: = P ^.

NEXT;

P ^.

Next: = Q ^.

NEXT;

Dispose (Q);

DEC (L.

Len;

END;

4. Insert operation of the double-linked list (insertion of new node Q)

P: = LOC (L, I);

NEW (q);

Q ^.

Data: = x;

Q ^ .pre: = P;

Q ^.

Next: = p ^.

NEXT;

P ^.

Next: = q;

Q ^.

NEXT ^ .pre: = q;

5. Double-linked list of deletions

P: = LOC (L, I); {p is the node to delete}

p ^ .pre ^.

Next: = p ^.

NEXT;

P ^.

Next ^ .pre: = p ^ .pre;

Dispose (P);

Key path (longest):

Var a, b: array [1..10, 1..10] of integer;

N, Last, Out: integer;

q, c: array [1..10] of integer;

o:

SET OF 1..10;

PROCEDURE INIT;

Var i, J: integer;

Begin

Readln (n);

For i: = 1 to n

DO

For j: = 1 to n

DO

READ (A [i, j]);

Last: = 0;

o: = []; OUT: = 0;

B: = a;

END;

Procedure sort;

Var i, J: integer;

p: boolean;

Begin

While Out <> n

Do Begin

For i: = 1 to n

DO

IF not (i

IN O)

Then Begin

P: =

True;

For j: = 1 to n

DO

IF a [j, i] = 1

Then Begin

P: =

False;

Break;

END;

IF P

Then Begin

INC; LAST

q [last]: = i;

INC; OUT;

o: = O [i];

Fillchar (a [i], sizeof (a [i]), 0);

END;

END;

END;

END;

Procedure Work_1;

Var i, j, t, k: integer;

Begin

A: = B; C [1]: = 0;

For i: = 1 to n

Do Begin

K: = 0;

For j: = 1 to i-1

DO

IF (a [q [j], q [i]]> 0) AND (a [q [j], q [i]] c [q [j]]> k)

THEN K: = a [q [j], q [i]] c [q [j]];

C [Q [I]]: = K;

END;

END;

Procedure Work_2;

Var i, j, k: integer;

Begin

Writeln (q [n]);

For i: = n-1 Downto 1

Do Begin

K: = Maxint;

For j: = i 1 to n

DO

IF (a [q [i], q [j]> 0) AND (C [q [j]] - a [q [i], q [j]]

THEN K: = C [q [j]] - a [q [i], q [j]];

IF C [q [i]] = k

THEN WRITELN (q [i], '');

C [Q [I]]: = K;

END;

END;

Begin

Init;

Sort;

Work_1;

Work_2;

End.

Topology Sort:

Var A: Array [1..100, 1..100] OF 0..1;

N: integer;

P:

Set of 1..100;

PROCEDURE INIT;

Var i, j, k: integer;

Begin

Fillchar (A, SizeOf (a), 0);

Readln (n);

For i: = 1 to n

Do Begin

READ (K);

While K <> 0

Do Begin

a [i, k]: = 1;

READ (K);

END;

END;

P: = [];

END;

PROCEDURE SECH;

VAR i, J, T, SUM, Printed: integer

Begin

Printed: = 0;

While Printed

DO

For i: = 1 to n

Do Begin

SUM: = 0;

For j: = 1 to n

Do Sum: = SUM A [J, I];

IF (SUM = 0) and not (i

in P)

The beginwrite (i, '');

P: = P [i];

Inc.

For t: = 1 to n

Do A [i, t]: = 0;

END;

END;

END;

Begin

Init;

Search;

End.