最小树形图 朱刘算法模板+建边技巧

http://acm.hdu.edu.cn/showproblem.php?pid=4966

把每个状态（LV，课程）当成一个点，全部连起来，然后给同一节课高等级的点向低等级连一条权值为0的边，最后创一个虚根连向所有的LV0，

用一个最简单的进制映射，类似ax+b hash

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
const int maxn = 100000 + 100;
const int INF = 2147480000;

struct Edge {
    int from, to;
    long long w;
}edges[maxn];
int sz;
int a[100], sum[100];
int N, M;
void add_edge(int from, int to, long long w) {
    ++sz;
    edges[sz].from = from; edges[sz].to = to; edges[sz].w = w;
}
int pre[maxn];//存储父节点
int vis[maxn];//标记作用
int id[maxn];//id[i]记录节点i所在环的编号
int in[maxn];//in[i]记录i入边中最小的权值
long long zhuliu(int root, int n, int m, Edge *edge)//root根 n点数 m边数
{
    long long res = 0;
    int u, v;
    while (1)
    {
        for (int i = 0; i < n; i++)
            in[i] = INF;//初始化
        for (int i = 1; i <= m; i++)
        {
            Edge E = edge[i];
            if (E.from != E.to && E.w < in[E.to])
            {
                pre[E.to] = E.from;//记录前驱
                in[E.to] = E.w;//更新
            }
        }
        for (int i = 0; i <n; i++)
            if (i != root && in[i] == INF)
                return -1;//有其他孤立点 则不存在最小树形图
                          //找有向环
        int tn = 0;//记录当前查找中 环的总数
        memset(id, -1, sizeof(id));
        memset(vis, -1, sizeof(vis));
        in[root] = 0;//根
        for (int i = 0; i <n; i++)
        {
            res += in[i];//累加
            v = i;
            //找图中的有向环 三种情况会终止while循环
            //1,直到出现带有同样标记的点说明成环
            //2,节点已经属于其他环
            //3,遍历到根
            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] = tn;//记录节点所属的 环编号
                id[v] = tn++;//记录节点所属的 环编号  环编号累加
            }
        }
        if (tn == 0) break;//不存在有向环
                           //可能存在独立点
        for (int i = 0; i <n; i++)
            if (id[i] == -1)
                id[i] = tn++;//环数累加
                             //对有向环缩点  和SCC缩点很像吧
        for (int i = 1; i <= m; i++)
        {
            v = edge[i].to;
            edge[i].from = id[edge[i].from];
            edge[i].to = id[edge[i].to];
            //<u, v>有向边
            //两点不在同一个环 u到v的距离为 边权cost - in[v]
            if (edge[i].from != edge[i].to)
                edge[i].w -= in[v];//更新边权值 继续下一条边的判定
        }
        n = tn;//以环总数为下次操作的点数 继续执行上述操作 直到没有环
        root = id[root];
    }
    return res;
}

int main() {
    while (scanf("%d%d", &N, &M) != EOF && N&&M) {
        sz = 0;
        sum[0] = 0;
        for (int i = 1; i <= N; i++) {
            scanf("%d", &a[i]);
            sum[i] = sum[i - 1] + a[i] + 1;
        }

        int c, L1, d, L2;
        long long w;
        for (int i = 1; i <= M; i++) {
            scanf("%d%d%d%d%lld", &c, &L1, &d, &L2, &w);
            /* for(int j=L1;j<=a[c];j++){
            add_edge(sum[c-1]+j+1,sum[d-1]+L2+1,w);
            }*/
            add_edge(sum[c - 1] + L1 + 1, sum[d - 1] + L2 + 1, w);
        }
        for (int i = 1; i <= N; i++) {
            add_edge(0, sum[i - 1] + 1, 0);
        }
        for (int i = 1; i <= N; i++) {
            for (int j = 0; j<a[i]; j++) {
                add_edge(sum[i - 1] + j + 2, sum[i - 1] + j + 1, 0);
            }
        }
        long long ans = zhuliu(0, sum[N] + 1, sz, edges);
        printf("%lld
", ans);
    }
    return 0;
}