HDU：GGS-DDU

题目链接：

题目大意：有$n$个课程，初始都在等级$0$，每个课程需要达到等级$a[i]$.满足$x$课程等级大于等于$dx$时，可花费$w$使得$y$课程等级达到$dy$，求最少需要多少钱？

最小树形图

一个有向图若存在从某个点开始的到达所有的的一个最小生成树，则它就是最小树形图。

引自

为每个课程的每个等级设置结点，若$x$课程等级大于等于$dx$时，可花费$w$使得$y$课程等级达到$dy$，则

建一条从$x$课程等级等于$dx$的点到$y$课程等级等于$dy$的点，长度为$w$的有向边.

因为课程等级是向下兼容的，即等级高的点可以无消耗达到等级低的点，故每个课程等级高的点向等级低的点建长度为$0$的边.

从而，求最小代价转化为了求整张图的最小树形图（若某课程达到最高等级那么一定可以达到较低等级）.

求最小树形图的复杂度为$O(VE)$.

代码如下：

1 #include 
     
        2 #include 
      
         3 #include 
       
          4 #define N 55  5 #define MAXN 25055  6 #define MAXM 30000  7 using namespace std;  8 const int inf=10000000;  9 int n,m,a[N]; 10 struct ZL{ 11     int n,m; 12     int pre[MAXN],id[MAXN],vis[MAXN]; 13     int inEdge[MAXN]; 14     struct Edge{ 15         int u,v; 16         int w; 17     }edge[MAXM]; 18     void init(int n_){ 19         n=n_;m=0; 20     } 21     void addedge(int u,int v,int w){ 22         edge[m].u=u; 23         edge[m].v=v; 24         edge[m].w=w; 25         m++; 26     } 27     int Directed_MST(int root){ 28         int ans=0,u,v; 29         while(1){ 30             for(int i=0;i