1851: 最小费用最大流

求一个网络的最小费用最大流

第1行：2个空格分开的整数N，M。N是节点数，M是边数。N≤500，M≤N^2/2
第2..M+1行：每行4个空格分开的整数A，B，C，D，表示了一条有向边A-B，边的容量为C，费用为D

第1行：一个整数，表示最小费用

50 1007
1 3 11 0
1 4 2 2
1 5 11 7
1 6 2 3
1 7 2 7
1 8 6 2
1 9 1 1
1 10 4 4
1 11 1 5
1 12 16 2
1 13 11 1
1 14 8 3
1 15 8 3
1 16 4 5
1 17 14 2
1 18 11 2
1 19 2 5
1 20 8 4
1 21 16 6
1 22 5 5
1 23 7 5
1 24 5 0
1 25 2 5
1 26 3 1
1 27 7 1
1 28 20 2
1 29 4 0
1 30 13 4
1 31 2 2
1 32 11 0
1 33 12 3
1 34 1 6
1 36 15 7
1 38 9 0
1 39 19 1
1 40 3 0
1 41 10 5
1 42 3 5
1 44 12 1
1 45 6 4
1 46 7 4
1 49 10 6
1 50 4 5
2 3 5 5
4 2 1 5
6 2 5 3
2 9 13 2
2 10 5 5
2 11 25 3
13 2 6 6
14 2 4 2
15 2 5 2
16 2 4 2
2 17 4 4
18 2 10 3
2 19 5 5
2 20 1 0
21 2 2 7
2 22 4 0
2 24 6 6
25 2 3 5
2 26 11 4
27 2 12 4
2 28 6 2
29 2 6 1
30 2 3 3
2 31 5 2
2 33 3 7
35 2 1 1
36 2 3 0
2 37 1 6
2 38 4 3
39 2 11 0
2 40 6 1
2 41 8 3
42 2 4 5
2 43 4 4
2 44 7 2
2 45 8 4
48 2 16 5
49 2 12 3
2 50 4 1
4 3 25 1
3 5 5 7
3 6 1 4
7 3 11 1
9 3 2 5
10 3 2 6
11 3 16 5
12 3 6 2
13 3 22 2
14 3 1 1
3 15 19 2
3 16 5 7
17 3 9 2
3 18 4 3
19 3 14 2
3 21 4 4
3 22 1 7
23 3 3 1
24 3 14 1
25 3 1 1
3 26 9 1
3 27 1 7
3 28 3 3
3 29 2 1
3 31 3 5
3 32 8 3
35 3 9 3
36 3 6 3
37 3 8 3
3 38 1 6
3 39 1 0
3 40 6 1
41 3 7 5
3 42 13 6
43 3 1 0
3 44 2 3
46 3 7 2
3 50 16 2
4 5 3 5
6 4 5 4
4 8 10 5
4 9 14 5
10 4 8 3
4 11 3 0
4 12 7 2
14 4 8 7
15 4 3 5
16 4 11 7
17 4 1 2
4 18 18 2
19 4 10 0
4 21 1 1
4 22 7 0
23 4 5 7
24 4 16 7
25 4 2 1
4 26 3 7
4 28 15 3
29 4 10 1
30 4 2 2
31 4 2 2
32 4 1 4
4 33 12 5
35 4 8 2
36 4 5 6
4 37 6 5
38 4 13 6
4 39 9 7
40 4 11 2
41 4 1 2
42 4 11 6
4 44 5 0
45 4 9 5
47 4 11 1
49 4 10 2
4 50 7 0
5 7 9 6
8 5 7 6
9 5 9 0
12 5 15 2
15 5 8 6
16 5 11 2
17 5 3 4
18 5 10 5
5 19 8 5
21 5 17 3
22 5 5 3
5 23 19 1
24 5 7 3
25 5 18 1
26 5 9 4
27 5 5 0
5 28 10 5
5 29 6 4
5 30 26 0
5 31 1 4
5 32 10 7
5 34 14 2
5 35 3 0
5 36 5 0
5 37 4 3
5 38 10 5
39 5 2 3
5 40 2 2
41 5 2 5
42 5 1 2
43 5 12 2
44 5 3 6
45 5 4 4
5 46 9 5
5 47 3 1
48 5 12 2
49 5 2 5
5 50 3 2
7 6 2 0
8 6 4 0
6 9 14 7
10 6 15 0
6 11 10 3
6 12 3 3
6 13 20 5
6 14 5 4
15 6 7 6
6 16 6 2
17 6 5 2
6 18 2 0
19 6 3 0
21 6 7 6
22 6 3 3
23 6 9 5
6 25 15 0
6 26 10 4
6 27 16 5
28 6 17 2
6 29 8 7
6 30 2 5
31 6 7 3
6 32 13 2
33 6 9 6
34 6 14 5
6 35 4 6
36 6 3 1
37 6 15 4
6 38 18 4
40 6 8 3
6 41 4 5
6 42 15 4
44 6 5 0
6 45 5 6
47 6 3 0
6 48 17 3
49 6 8 3
6 50 12 4
7 9 11 1
7 10 4 1
7 11 7 5
12 7 3 7
13 7 3 0
15 7 8 4
16 7 2 3
7 18 3 3
19 7 10 4
20 7 2 6
7 21 2 3
7 22 15 7
23 7 8 3
7 24 6 5
7 25 15 0
27 7 6 5
7 28 4 2
29 7 8 1
31 7 6 3
7 32 3 6
33 7 6 1
7 35 5 5
7 36 10 4
37 7 4 0
7 38 6 6
7 39 13 3
7 40 5 0
7 41 10 1
7 42 5 1
7 44 10 6
45 7 3 3
7 46 8 1
7 47 1 6
7 49 24 3
7 50 9 3
8 9 2 1
8 10 5 4
11 8 4 0
12 8 7 3
8 14 2 2
15 8 18 5
8 17 8 4
8 18 2 6
8 19 9 0
8 21 3 1
8 22 3 5
23 8 16 1
25 8 13 6
27 8 13 0
28 8 4 7
32 8 7 3
34 8 11 4
8 35 15 0
8 36 8 1
8 37 17 2
8 38 9 6
8 39 9 5
8 40 3 3
8 41 10 0
8 42 2 7
43 8 2 6
8 44 5 3
8 49 1 7
8 50 2 6
9 10 19 1
11 9 10 0
9 12 18 1
9 13 7 5
14 9 10 7
9 15 11 3
9 16 8 0
9 17 5 1
19 9 1 7
20 9 6 3
21 9 7 7
9 22 14 7
9 23 7 3
9 25 4 4
26 9 10 6
27 9 4 6
28 9 7 7
29 9 2 6
31 9 7 0
33 9 6 1
34 9 6 3
9 35 2 4
9 36 9 0
37 9 6 2
9 39 2 7
40 9 10 2
9 41 3 2
42 9 2 6
44 9 9 7
9 45 3 7
9 46 6 5
9 47 10 5
48 9 8 7
49 9 1 2
13 10 8 2
10 14 13 0
16 10 5 3
10 17 1 1
18 10 1 0
10 19 6 7
20 10 18 0
10 21 9 2
10 22 3 2
10 23 9 0
24 10 21 3
10 25 5 7
26 10 9 3
28 10 14 5
29 10 13 7
10 31 9 3
10 33 17 3
34 10 4 5
10 35 2 7
36 10 10 2
37 10 4 6
38 10 4 2
10 40 6 0
41 10 3 1
42 10 1 1
43 10 1 0
10 44 16 2
46 10 25 2
47 10 2 6
10 48 10 1
10 49 3 1
12 11 7 1
13 11 1 2
11 14 9 2
11 15 5 1
17 11 10 2
18 11 4 6
11 19 17 0
11 20 2 5
11 22 5 7
11 23 5 4
11 25 1 2
26 11 3 3
27 11 7 2
11 28 2 6
11 29 10 5
30 11 14 6
33 11 9 5
11 34 3 4
36 11 8 6
11 37 10 1
38 11 2 6
39 11 1 2
11 41 10 2
42 11 7 3
43 11 3 4
11 45 5 0
11 46 11 1
47 11 4 4
49 11 22 7
13 12 10 0
12 15 1 6
16 12 8 0
12 17 8 0
12 18 9 6
20 12 16 0
21 12 9 6
22 12 13 3
23 12 3 6
24 12 4 2
25 12 4 6
12 26 22 3
12 27 8 7
28 12 3 4
12 29 9 2
12 30 10 7
32 12 10 1
34 12 16 6
12 35 9 3
12 36 6 4
38 12 3 4
39 12 3 5
40 12 1 5
12 42 10 7
12 43 11 5
12 44 8 3
12 45 5 4
12 46 2 1
12 47 11 3
12 48 14 2
16 13 4 6
13 18 2 0
13 19 3 4
13 20 12 7
13 21 1 7
13 22 7 0
13 23 1 1
13 25 5 5
26 13 11 4
27 13 6 7
13 28 5 4
29 13 7 2
13 32 5 7
13 33 17 3
13 34 2 1
13 35 15 7
36 13 4 5
37 13 5 5
13 38 10 0
39 13 2 1
13 40 10 2
41 13 5 5
42 13 7 1
43 13 5 2
44 13 2 0
45 13 8 0
46 13 3 3
47 13 9 7
48 13 19 3
13 49 2 2
13 50 2 2
14 15 10 7
16 14 5 7
18 14 11 5
19 14 6 1
14 21 7 1
14 22 7 6
23 14 6 4
14 24 2 1
14 25 2 6
26 14 12 4
14 27 8 5
28 14 2 7
14 29 15 0
30 14 7 3
31 14 14 1
14 32 4 5
33 14 5 4
34 14 3 6
14 35 3 7
36 14 7 6
37 14 7 3
38 14 2 5
39 14 4 4
40 14 10 3
41 14 18 7
14 42 10 2
43 14 8 4
14 44 10 6
45 14 10 5
48 14 7 0
14 49 10 7
14 50 6 7
16 15 6 3
15 17 7 1
18 15 6 1
15 19 5 3
15 20 1 1
21 15 1 5
22 15 6 6
23 15 7 5
15 24 24 1
15 25 12 2
15 26 7 4
27 15 6 6
28 15 1 2
29 15 9 0
15 30 2 7
15 31 5 5
15 32 5 7
15 33 8 2
15 34 8 4
15 35 5 2
15 36 14 2
37 15 2 7
15 38 11 7
39 15 4 6
15 41 7 7
15 42 12 4
15 43 5 3
15 45 5 5
46 15 9 3
15 47 2 6
15 48 7 6
15 49 10 1
15 50 2 1
17 16 3 7
18 16 25 5
19 16 4 4
20 16 16 0
21 16 1 4
16 22 4 0
16 23 3 0
24 16 5 5
25 16 2 1
26 16 4 5
16 27 3 2
29 16 10 0
16 30 3 4
32 16 5 7
33 16 8 0
16 35 10 2
16 36 7 3
16 37 6 4
38 16 9 0
39 16 7 3
16 40 16 1
16 41 12 5
42 16 7 7
43 16 9 3
44 16 29 3
16 45 10 2
16 46 5 4
16 47 4 2
16 49 7 0
16 50 8 2
17 19 8 0
20 17 4 1
22 17 9 3
17 23 14 1
17 24 2 5
17 25 10 3
17 26 7 4
17 27 15 4
17 28 10 5
29 17 8 2
17 30 2 6
17 31 10 6
32 17 1 2
17 33 6 4
17 34 6 6
35 17 8 2
36 17 10 4
17 37 12 2
38 17 1 2
39 17 4 5
40 17 19 3
17 41 22 5
42 17 16 1
17 43 9 1
17 44 20 2
17 45 16 4
46 17 13 3
47 17 5 7
49 17 1 6
17 50 14 6
18 19 6 7
18 20 2 4
18 21 1 7
24 18 1 2
18 25 5 2
26 18 10 2
27 18 8 3
18 28 6 6
18 29 4 0
32 18 2 2
18 33 1 4
18 34 7 0
18 35 4 4
36 18 13 5
39 18 7 4
18 41 4 3
43 18 4 5
18 44 26 3
49 18 8 7
18 50 3 0
19 20 12 6
19 21 20 4
19 22 4 0
19 23 9 7
24 19 2 0
19 25 10 1
26 19 12 0
19 27 3 4
19 28 19 5
19 29 9 7
30 19 10 2
31 19 11 2
19 32 2 6
19 33 24 0
19 34 6 7
19 35 3 5
19 36 12 6
37 19 8 1
19 39 5 1
40 19 7 0
19 41 5 6
19 42 15 3
43 19 1 4
19 44 2 1
19 45 10 1
46 19 22 6
19 47 1 6
48 19 4 4
49 19 5 3
19 50 23 2
20 21 2 6
22 20 2 7
20 23 8 5
20 24 4 2
20 25 4 2
20 26 24 7
28 20 2 6
20 29 2 4
20 30 4 1
20 31 4 2
20 32 7 0
33 20 7 4
35 20 17 0
20 36 3 2
37 20 5 6
38 20 7 5
20 40 9 7
41 20 5 0
42 20 3 4
43 20 1 7
20 45 5 1
46 20 7 2
20 47 4 0
48 20 7 2
20 49 24 7
20 50 2 4
22 21 7 2
24 21 3 1
25 21 12 7
21 26 11 7
21 27 11 6
28 21 3 7
21 29 16 5
21 30 18 4
31 21 1 0
32 21 12 7
21 34 13 5
35 21 8 3
21 37 6 2
38 21 20 7
21 39 3 4
40 21 6 3
21 41 5 3
21 42 6 5
43 21 11 2
44 21 8 4
21 45 16 6
21 46 21 7
21 47 5 5
48 21 5 6
21 50 1 1
23 22 6 1
24 22 8 2
22 26 14 4
22 27 4 0
28 22 3 7
22 29 11 7
33 22 7 3
22 34 9 2
35 22 15 7
22 37 9 0
22 38 12 4
39 22 5 7
22 40 1 2
41 22 5 2
42 22 19 5
22 43 7 0
22 44 16 3
22 45 12 7
22 46 11 1
47 22 4 4
22 48 6 1
22 50 1 6
24 23 25 4
25 23 6 2
27 23 1 0
29 23 2 2
32 23 10 2
23 33 11 1
23 34 10 7
23 35 12 6
36 23 11 4
23 37 28 7
23 39 7 5
23 40 1 1
41 23 9 2
23 46 11 6
47 23 2 4
23 48 8 7
23 50 9 2
24 25 2 0
24 27 4 6
28 24 5 2
29 24 7 3
24 30 10 2
24 31 13 1
24 32 9 2
24 33 5 5
24 34 6 0
24 35 9 6
24 36 7 7
37 24 5 6
24 38 15 5
39 24 9 1
24 40 15 1
24 41 14 7
24 43 4 6
44 24 16 6
46 24 7 0
48 24 2 6
49 24 16 0
24 50 5 3
26 25 23 5
27 25 3 2
25 28 4 1
29 25 5 6
30 25 18 6
25 32 4 4
25 33 9 0
25 34 23 1
25 35 10 2
36 25 7 3
25 37 2 6
25 38 6 0
39 25 1 4
42 25 7 3
44 25 6 1
46 25 6 4
47 25 1 4
48 25 4 2
49 25 8 1
27 26 10 2
28 26 5 5
30 26 4 7
31 26 8 4
26 32 3 6
33 26 6 5
26 34 11 5
35 26 10 4
36 26 6 7
26 37 2 2
26 38 7 5
39 26 16 5
40 26 12 1
26 41 1 3
42 26 5 7
43 26 3 0
44 26 2 2
45 26 10 1
46 26 3 6
26 47 5 7
48 26 7 2
26 49 5 2
26 50 7 0
27 28 2 1
27 29 7 5
31 27 11 3
27 32 13 4
33 27 8 3
36 27 1 7
27 40 3 3
41 27 5 0
27 43 1 3
44 27 6 2
45 27 19 7
27 46 15 3
48 27 6 3
27 49 9 7
27 50 2 2
30 28 11 1
31 28 6 4
32 28 2 3
28 33 10 5
28 34 1 3
28 35 3 3
37 28 6 4
38 28 1 3
28 39 2 5
41 28 1 4
28 43 1 1
44 28 10 2
45 28 5 5
47 28 13 4
48 28 1 3
28 49 11 1
28 50 9 1
29 30 17 6
29 32 26 7
33 29 13 7
35 29 5 0
29 37 10 5
39 29 5 4
29 40 13 2
29 41 12 3
29 42 22 0
29 44 10 6
46 29 6 3
47 29 16 6
29 48 7 0
29 49 18 4
29 50 1 0
31 30 5 0
32 30 10 7
30 33 21 6
30 35 1 4
30 36 7 6
37 30 11 4
38 30 9 0
30 39 9 0
30 41 6 5
42 30 9 2
30 44 3 7
30 46 19 4
30 48 8 5
30 49 13 5
30 50 1 1
31 32 14 5
33 31 8 5
34 31 9 6
36 31 8 0
37 31 28 4
38 31 10 7
31 39 10 3
40 31 6 2
41 31 8 6
31 42 6 1
43 31 22 5
31 44 1 7
45 31 12 6
31 46 7 6
31 47 14 7
49 31 3 0
31 50 3 5
32 35 4 0
36 32 2 0
37 32 6 2
38 32 30 6
39 32 13 7
32 40 16 6
42 32 18 0
43 32 1 2
32 44 1 2
32 45 8 1
46 32 5 3
32 47 6 7
48 32 1 2
32 50 4 6
33 34 4 5
33 36 30 4
33 37 16 6
33 38 5 7
33 39 8 4
33 40 5 5
33 41 3 3
42 33 12 0
33 43 2 1
44 33 13 3
45 33 5 7
33 46 4 0
33 47 3 5
33 50 8 7
35 34 4 1
34 36 13 3
37 34 1 7
34 38 9 5
34 39 7 1
40 34 3 0
41 34 6 3
42 34 12 4
34 43 2 7
34 44 1 2
45 34 4 2
34 46 16 6
47 34 2 2
34 48 10 0
49 34 15 1
37 35 3 2
38 35 17 6
35 40 7 3
41 35 5 3
35 42 2 6
35 43 11 3
44 35 24 7
35 45 10 3
46 35 1 1
35 47 7 0
48 35 9 6
49 35 6 0
35 50 7 2
38 36 8 5
39 36 6 3
40 36 2 6
36 41 10 5
42 36 17 7
43 36 5 4
36 44 3 6
46 36 3 2
48 36 2 2
49 36 14 7
36 50 3 2
37 38 21 5
37 39 20 7
40 37 1 7
37 41 1 2
42 37 3 3
44 37 7 5
45 37 17 3
46 37 2 0
37 47 9 2
37 48 10 7
49 37 3 3
37 50 13 3
38 39 8 4
40 38 11 4
38 42 14 1
43 38 9 6
38 44 12 1
38 45 7 2
38 46 29 3
38 47 2 4
38 48 14 6
38 49 8 2
38 50 8 7
41 39 8 3
42 39 15 4
39 43 2 7
45 39 1 6
39 46 6 4
47 39 9 5
39 50 9 1
41 40 10 3
43 40 12 3
40 44 2 6
45 40 6 1
46 40 9 0
47 40 17 0
48 40 2 0
40 49 15 1
40 50 6 4
42 41 4 0
41 43 1 0
41 44 15 2
45 41 12 6
41 46 19 2
47 41 11 6
41 48 13 7
41 49 9 0
41 50 5 2
42 43 1 2
44 42 7 2
45 42 9 6
42 46 5 7
47 42 5 7
42 48 4 4
42 50 13 6
43 44 1 6
43 45 11 4
46 43 8 3
43 48 1 3
43 49 8 1
43 50 17 7
45 44 8 0
44 46 8 5
47 44 3 2
48 44 6 5
44 49 8 2
44 50 6 1
45 46 5 3
45 47 4 2
46 48 10 3
49 46 8 2
46 50 1 3
48 47 31 0
49 47 10 1
47 50 12 3
48 49 2 4
48 50 13 0
49 50 8 1

1682