題意：
? ? ? 以一些科目，和輔導班，每個科目最終要求修到某個等級，可以花一定的錢在輔導班把某一科目修到某一等級，進入輔導班的時候會有一個限制，那就是達到他給出的科目和等級限制，比如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\n",T.directedMST(0 ,sum[n] ,tt)); }return 0; }

總結

以上是生活随笔為你收集整理的hdu4966 最小树形图（最少辅导花费）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。