hdu 4966 最小树形图

将每门课等级拆成0，1,2,3...a[i]个点，对每一个等级大于0的点向它低一级连边，权值为0【意思是，若修了level k。则level(0~k)都当做修了】

将输入的边建边，权值为money[i]。

建立根节点，向每一个level 0的点连边，权值为0【由于初始level 0的都修了】

因为题目要求每门课都必须达到最大level，也就是相应图中根节点能到达全部点，问题就变成了求有向图的最小生成树。

#include<iostream>

#include<cstdio>

#include<cstring>

#include<string>

#include<algorithm>

using namespace std;

#define INF 0x3FFFFFF

#define MAXN 5555

struct edge

{

	int  u,v,w;

}e[9999999];

int n,en;

int pre[MAXN],in[MAXN],id[MAXN],vis[MAXN];

void add(int u,int v,int w)

{

	e[en].u=u;

	e[en].v=v;

	e[en++].w=w;

}

int zl(int root ,int vn)

{

	int ans=0;

	int cnt;

	while(1)

	{

		for(int i=0;i<vn;i++)

			in[i]=INF,id[i]=-1,vis[i]=-1;

		for(int i=0;i<en;i++)

		{

			if(in[e[i].v]>e[i].w && e[i].u!=e[i].v)

			{

				pre[e[i].v]=e[i].u;

				in[e[i].v]=e[i].w;

			}

		}

		in[root]=0;

		pre[root]=root;

		for(int i=0;i<vn;i++)

		{

			ans+=in[i];

			if(in[i]==INF)

				return -1;

		}

		cnt=0;

		for(int i=0;i<vn;i++)

		{

			if(vis[i]==-1)

			{

				int t=i;

				while(vis[t]==-1)

				{

					vis[t]=i;

					t=pre[t];

				}

				if(vis[t]!=i || t==root) continue;

				for(int j=pre[t];j!=t;j=pre[j])

					id[j]=cnt;

				id[t]=cnt++;

			}

		}

		if(cnt==0) break;

		for(int i=0;i<vn;i++)

			if(id[i]==-1)

				id[i]=cnt++;

		for(int i=0;i<en;i++)

		{

			int u,v;

			u=e[i].u;

			v=e[i].v;

			e[i].u=id[u];

			e[i].v=id[v];

			e[i].w-=in[v];

		}

		vn=cnt;

		root=id[root];

	}

	return ans;

}

int a[MAXN],pres[MAXN];

int main()

{

    int x,y,b,c,d,m;

    while(~scanf("%d%d",&n,&m))

    {

        if(!n&&!m) break;

        for(int i=1;i<=n;i++)

            scanf("%d",&a[i]),

            pres[i]=pres[i-1]+a[i]+1;

        en=0;

        int s=0;

        int t=pres[n]+1;

        for(int i=1;i<=n;i++)

        {

            for(int id=1;id<=a[i];id++)

            {

                add(pres[i-1]+id+1,pres[i-1]+id,0);

          //      printf("%d -> %d\n",pres[i-1]+id+1,pres[i-1]+id);

            }

            add(s,pres[i-1]+1,0);

       //     printf("%d -> %d\n",pres[i-1]+a[i]+1,t);

       //     printf("%d -> %d\n",s,pres[i-1]+1);

        }

        for(int i=1;i<=m;i++)

        {

            scanf("%d%d%d%d%d",&x,&y,&b,&c,&d);

            add(pres[x-1]+y+1,pres[b-1]+c+1,d);

    //        printf("%d -> %d\n",pres[x-1]+y+1,pres[b-1]+c+1);

        }

        int tmp=zl(0,t);

        if(tmp<0) puts("-1");

        else printf("%d\n",tmp);

    }

	return 0;

}