以一些科目，和辅导班，每个科目最终要求修到某个等级，可以花一定的钱在辅导班把某一科目修到某一等级，进入辅导班的时候会有一个限制，那就是达到他给出的科目和等级限制，比如a b c d m的意思就是科目a必须达到b等级才可以花m钱把科目c修到d等级，最后问把所有科目修到给定的等级要花的最小辅导费用。
思路：
我们可以把每一个科目的每一个等级看成一个点，然后根据给定的关系，把等级和等级之间的边和权建立起来，然后再把非0等级建一条当前等级-1的边，费用为0，意思是修了当前等级，之前的等级也算是修完了，最后在虚拟出来一个点，连接所有等级0的点，意思是最开始0等级的已经修完了，然后一遍最小树形图就行了，对于最小树形图，他其实就是在求有向图的最小生成树，用的是 朱-刘 算法（我自己现在还不了解那个算法，只是直接粘模板而已，自己一直感觉不到这个算法的正确性）。
#include<stdio.h> #include<string.h> //****************************************** const int maxm=2000000; //边的个数 const int maxn=25100; //点的个数 const int inf=0x3f3f3f3f; typedef struct { int u,v,w; }EDGE; EDGE e[maxm]; int pre[maxn],id[maxn],vis[maxn],in[maxn]; typedef struct { int directedMST(int root ,int n ,int m) { //从0开始用的 0....N,m条边 int res=0,nv=n + 1,i; while (1) { for (i=0;i<nv;i++) { in[i]=inf; } for (i=1;i<=m;i++) { int u=e[i].u; int v=e[i].v; if (e[i].w<in[v]&&u!=v) { pre[v]=u; in[v]=e[i].w; } } for (i=0;i<nv;i++) { if (i==root)continue; if (in[i]==inf)return -1; } int cntnode=0; memset(id,-1,sizeof(id[0])*(nv+3)); memset(vis,-1,sizeof(vis[0])*(nv+3)); in[root]=0; for (i=0;i<nv;i++) { res+=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]=cntnode; } id[v]=cntnode++; } } if (cntnode==0)break; for (i=0;i<nv;i++) { if (id[i]==-1)id[i]=cntnode++; } for (i=1;i<=m;i++) { int v=e[i].v; e[i].u=id[e[i].u]; e[i].v=id[e[i].v]; if (e[i].u!=e[i].v) { e[i].w-=in[v]; } } nv=cntnode; root=id[root]; } return res; } }M_Tree; //*************************************** int sum[55]; int num[55]; int main () { int n ,m ,i ,j; int a ,b ,c ,d ,mo; M_Tree T; while(~scanf("%d %d" ,&n ,&m) && n + m) { sum[0] = 0; for(i = 1 ;i <= n ;i ++) { scanf("%d" ,&num[i]); num[i] ++; sum[i] = sum[i-1] + num[i]; } int tt = 0; while(m--) { scanf("%d %d %d %d %d" ,&a ,&b ,&c ,&d ,&mo); b++ ,d ++; for(int i = sum[a-1] + b ;i <= sum[a] ;i ++) { e[++tt].u = i; e[tt].v = sum[c-1] + d; e[tt].w = mo; } } for(i = 1 ;i <= n ;i ++) { for(j = sum[i-1] + 2 ;j <= sum[i] ;j ++) { e[++tt].u = j; e[tt].v = j-1; e[tt].w = 0; } e[++tt].u = 0; e[tt].v = sum[i-1] + 1; e[tt].w = 0; } printf("%d ",T.directedMST(0 ,sum[n] ,tt)); } return 0; }