题意：
你有n个课程 每个课程有一个规定的毕业学分 修学分有m种方式 每种方式要求先修到x课程x'学分以上才能花费money去修y课程并且将学分修到y' 问 最少花费多少可以毕业
思路：
一开始想费用流 建完图发现一个问题解决不掉 那就是 一条边如果流过多次怎样才能让费用只计算一次 所以换思路
我们知道 为了应付“ 学分修到y' ”这个条件 高层学分一定要“覆盖”低层学分 那么就想到以每个学分为一个点 高层向低层连边 费用为0 同时修学分的方式是输入的 直接建边 费用为输入费用 一开始只能走到0学分 所以超级源点向所有0学分连边 费用0 那么此时我们想要的是从源点花最小费用走到所有点 这就是有向图最小生成树 即最小树形图
代码：
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
#define M 610
#define inf 2000000000int n, m, ans, tot, S;
int head[M], id[M], in[M], pre[M], vis[M], node[M][M], s[M];
struct ed {int u, v, w, next;
} ed[M * M];int ZL(int root, int V, int E) {int ret = 0;for (;;) {for (int i = 0; i < V; i++) {id[i] = -1;vis[i] = -1;in[i] = inf;}for (int i = 0; i < E; i++) {int u = ed[i].u;int v = ed[i].v;if (ed[i].w < in[v] && u != v) {pre[v] = u;in[v] = ed[i].w;}}for (int i = 0; i < V; i++) {if (i == root)continue;if (in[i] == inf)return -1;}int cnt = 0;in[root] = 0;for (int i = 0; i < V; i++) {ret += in[i];int v = i;while (vis[v] != i && id[v] == -1 && v != root) {vis[v] = i;v = pre[v];}if (v != root && id[v] == -1) {for (int u = pre[v]; u != v; u = pre[u])id[u] = cnt;id[v] = cnt++;}}if (cnt == 0)break;for (int i = 0; i < V; i++)if (id[i] == -1)id[i] = cnt++;for (int i = 0; i < E; i++) {int u = ed[i].u;int v = ed[i].v;ed[i].u = id[u];ed[i].v = id[v];if (id[u] != id[v])ed[i].w -= in[v];}V = cnt;root = id[root];}return ret;
}void add(int U, int V, int W) {ed[tot].u = U;ed[tot].v = V;ed[tot].w = W;ed[tot].next = head[U];head[U] = tot++;
}int main() {int i, j, k, u, v, tmp;while (scanf("%d%d", &n, &m) != EOF) {if (!n && !m)break;k = 0;for (i = 1; i <= n; i++) {scanf("%d", &s[i]);for (j = 0; j <= s[i]; j++)node[i][j] = k++;}S = k++;tot = 0;memset(head, -1, sizeof(head));for (i = 1; i <= n; i++) {add(S, node[i][0], 0);for (j = 1; j <= s[i]; j++)add(node[i][j], node[i][j - 1], 0);}for (i = 1; i <= m; i++) {scanf("%d%d", &u, &v);tmp = node[u][v];scanf("%d%d", &u, &v);v = node[u][v];u = tmp;scanf("%d", &tmp);add(u, v, tmp);}ans = ZL(S, k, tot);printf("%d\n", ans);}return 0;
}
