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; }

总结

以上是生活随笔为你收集整理的hdu 4966 最小树形图的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。