HDU - 4966 GGS-DDU (最小树形图)

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

二叉树子树平均值的最大值。解题思路：每个科目的每个层次都看成一个点，每个科目的层次0和根连边，费用0
每个科目的高层次向下一个低层次连边，费用为0(因为你高层次的会了就表示低层次的也会了)
接着按要求连边就可以了
预处理还是挺麻烦的

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;const int MAXNODE = 1010;
const int MAXEDGE = 1000100;
typedef int Type;
const Type INF = 0x3f3f3f3f;struct Edge {int u, v;Type dis;Edge() {}Edge(int u, int v, Type dis): u(u), v(v), dis(dis) {}
};struct Directed_MT{int n, m;Edge edges[MAXEDGE];int vis[MAXNODE];int pre[MAXNODE];int id[MAXNODE];Type in[MAXNODE];void init(int n) {this->n = n;m = 0;}void AddEdge(int u, int v, Type dis) {edges[m++] = Edge(u, v, dis);}Type DirMt(int root) {Type ans = 0;while (1) {//初始化for (int i = 0; i < n; i++) in[i] = INF;for (int i = 0; i < m; i++) {int u = edges[i].u;int v = edges[i].v;//找寻最小入边，删除自环if (edges[i].dis < in[v] && u != v) {in[v] = edges[i].dis;pre[v] = u;}}for (int i = 0; i < n; i++) {if (i == root) continue;//如果没有最小入边，表示该点不连通，则最小树形图形成失败if (in[i] == INF) return -1;}int cnt = 0;//记录缩点memset(id, -1, sizeof(id));memset(vis, -1, sizeof(vis));in[root] = 0;//树根不能有入边for (int i = 0; i < n; i++) {ans += 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 < n; i++) if (id[i] == -1) id[i] = cnt++;for (int i = 0; i < m; i++) {int v = edges[i].v;edges[i].v = id[edges[i].v];edges[i].u = id[edges[i].u];if (edges[i].u != edges[i].v) edges[i].dis -= in[v];}//缩点完后，点的数量就边了n = cnt;root = id[root];}return ans;}
}MT;const int N = 60;
const int M = 600;
int n, m;
int level[N], Sum[N];
int dis[M][M];void init() {Sum[0] = 0;for (int i = 1; i <= n; i++) {scanf("%d", &level[i]);level[i]++;if (i == 1) Sum[i] = level[i];else Sum[i] = Sum[i - 1] + level[i];}Sum[n + 1] = Sum[n] + 1;MT.init(Sum[n + 1]);//跟根结点连边for (int i = 1; i <= n; i++)if (i == 1) MT.AddEdge(0, i, 0);else MT.AddEdge(0, Sum[i - 1] + 1, 0);//高层次的连向低层次的for (int i = 1; i <= n; i++) for (int j = level[i] - 1; j > 0; j--) MT.AddEdge(j + 1 + Sum[i - 1], j + Sum[i - 1], 0);memset(dis, 0x3f, sizeof(dis));int c, l1, d, l2, money;//课程for (int i = 1; i <= m; i++) {scanf("%d%d%d%d%d", &c, &l1, &d, &l2, &money);for (int u = Sum[c - 1] + 1 + l1; u <= Sum[c]; u++) {int v = Sum[d - 1] + l2 + 1;dis[u][v] = min(dis[u][v], money);}}//取课程的最小费用，连边for (int i = 1; i < Sum[n + 1]; i++)for (int j = 1; j < Sum[n + 1]; j++)if (dis[i][j] != INF)MT.AddEdge(i, j, dis[i][j]);printf("%d\n", MT.DirMt(0));
}int main() {while (scanf("%d%d", &n, &m) != EOF && n + m) {init();}return 0;
}