hdu 4966 最小樹形圖

hdu 4966 最小樹形圖

將每門課等級拆成0，1,2,3...a[i]個點，對每個等級大於0的點向它低一級連邊，權值為0【意思是，若修了level k，則level(0~k)都當做修了】

將輸入的邊建邊，權值為money[i]。

建立根節點，向每個level 0的點連邊，權值為0【因為初始level 0的都修了】

由於題目要求每門課都必須達到最大level，也就是對應圖中根節點能到達所有點，問題就變成了求無向圖的最小生成樹。

#include
#include
#include
#include
#include

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;ie[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 %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;
}