题目链接：传送门

Description

有一个人，想学习N个科目，每个科目都有相应的层次 有M个课程，M个课程的要求是，你的第c个科目的层次要达到l1，才可以参加，参加完这个课程后，你需要缴费money，但你的第d个科目的层次会达到l2 问如何花最少的钱，使得每个科目的层次都达到最高

Solution

每个科目的每个层次都看成一个点，每个科目的层次0和一个根连边，费用为0；每个科目的高层次向下一个低层次连边，费用为0(因为你高层次的会了就表示低层次的也会了) 然后用朱刘算法跑一遍最小树形图即可

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
124
125
126
127
128
129
#include <bits/stdc++.h>

using namespace std;

const int Maxn = 500 + 10, Maxm = 2500 + 10, inf = INT_MAX;

struct node
{
    int x, y, w;
}edge[Maxm];

int N, M, cnt, Ans, Index;
int Map[55][500 + 10];

inline void Init()
{
    cnt = Ans = Index = 0;
}

inline void add_edge (int x, int y, int z)
{
    edge[++cnt].x = x;
    edge[cnt].y = y;
    edge[cnt].w = z;
}

int In[Maxn], Pre[Maxn];
int id[Maxn], Vis[Maxn];

inline int Solve (int root)
{
    while (1)
    {
        for (int i = 1; i <= N; ++i) In[i] = inf;
        for (int i = 1; i <= cnt; ++i)
        {
            int x = edge[i].x, y = edge[i].y;
            if (x != y && edge[i].w < In[y])
            {
                Pre[y] = x;
                In[y] = edge[i].w;
            }
        }
        for (int i = 1; i <= N; ++i)
            if (i != root && In[i] == inf) return -1;

        int sum = 0;
        memset(id, -1, sizeof id);
        memset(Vis, -1, sizeof Vis);
        In[root] = 0;
        for (int i = 1; i <= N; ++i)
        {
            Ans += In[i];
            int now = i;
            while (Vis[now] != i && now != root && id[now] == -1)
            {
                Vis[now] = i;
                now = Pre[now];
            }

            if (now != root && id[now] == -1)
            {
                int tmp = Pre[now];
                ++sum;
                while (tmp != now)
                {
                    id[tmp] = sum;
                    tmp = Pre[tmp];
                }
                id[now] = sum;
            }
        }
        if (!sum) return Ans;

        for (int i = 1; i <= N; ++i)
            if (id[i] == -1) id[i] = ++sum;
        for (int i = 1; i <= cnt; ++i)
        {
            int x = edge[i].x, y = edge[i].y;
            edge[i].x = id[x]; edge[i].y = id[y];
            if (id[x] != id[y])
                edge[i].w -= In[y];
        }
        N = sum;
        root = id[root];
    }
}

int main()
{
#ifdef hk_cnyali
    freopen("A.in", "r", stdin);
    freopen("A.out", "w", stdout);
#endif
    while (1)
    {
        scanf("%d%d", &N, &M);
        if (N == M && !N) break;
        Init();
        for (int i = 1; i <= N; ++i)
        {
            int x;
            scanf("%d", &x);
            for (int j = 0; j <= x; ++j)
                Map[i][j] = ++Index;
            Map[i][501] = x;
        }
        while (M--)
        {
            int a, b, c, d, e;
            scanf("%d%d%d%d%d", &a, &b, &c, &d, &e);
            add_edge(Map[a][b], Map[c][d], e);
        }

        for (int i = 1; i <= N; ++i)
            for (int j = 1; j <= Map[i][501]; ++j)
            {
                add_edge(Map[i][j], Map[i][j - 1], 0);
            }

        for (int i = 1; i <= N; ++i)
            add_edge(0, Map[i][0], 0);

        N = Index;

        printf("%d\n", Solve(0));
    }
    return 0;
}