首页 > 代码库 > hdu4966 GGS-DDU --- 最小树形图
hdu4966 GGS-DDU --- 最小树形图
在比赛接近末尾的阶段听了题意,感觉信息量有点大,可能是贪心、dp之类的就懒得想了。。
哎。。要是往图论上想一点点说不定就。。
题意:
有n门课程,每门课程有0~a[i]个等级,开始都在0级。
有m个培训班,每个培训班的条件是第c门课等级>=l1,这样可以使第d门课的等级升到l2,并花费一定money。
问要使得所有课程都达到最高等级至少需要多少money。
根据条件建一个有向图,要想到每门课的高等级可以指向低等级,
那么就可以发现我们的目的是选择一些边使得每门课的0到a[i]都是联通的,
进一步可以发现可以把每门课不同level之间的边权为0,那么就是求该有向图上的最小生成树,
可以再添加一个附加根结点方便求解。
#include <iostream> #include <cstdlib> #include <cstring> #include <string> #include <cstdio> #include <cmath> #include <algorithm> #include <vector> #include <queue> #include <map> #define inf 0x3f3f3f3f #pragma comment(linker, "/STACK:16777216") #define eps 1e-6 #define ll long long using namespace std; const int maxm=30000; const int maxn=2600; struct node { int u,v,w; }e[maxm]; int in[maxn],vis[maxn],pre[maxn],a[maxn],ans,id[maxn],mk[maxn]; int zhuliu(int r,int V,int E)//树根 结点数 边数 { int cnt; memset(pre,-1,sizeof pre); ans=0;//最小树形图的权值 while(1) { int u,v,i; //找最小入边 for(i=0;i<=V;i++) in[i]=inf;//记该点入边最小的权值 for(i=0;i<E;i++) { u=e[i].u; v=e[i].v; if(e[i].w<in[v] && u!=v) { pre[v]=u;//记录权值最小入边的那个入点 in[v]=e[i].w; } } for(i=0;i<V;i++)//判断图不连通 直接返回 if(i!=r&&in[i]==inf) return -1; //找环 cnt=0;//记缩点后的联通块编号 memset(id,-1,sizeof id);//id[i]表示i缩点后在哪个联通块 memset(vis,-1,sizeof vis); in[r]=0; for(i=0;i<V;i++) { ans+=in[i]; v=i; while(vis[v]!=i&&v!=r&&id[v]==-1)//找环 { vis[v]=i; v=pre[v]; } if(v!=r&&id[v]==-1)//缩点 { for(u=pre[v];u!=v;u=pre[u]) id[u]=cnt; id[v]=cnt++; } } if(cnt==0) break;//无环则结束 //建新图 for(i=0;i<V;i++) if(id[i]==-1) id[i]=cnt++; for(i=0;i<E;i++) { u=e[i].u; v=e[i].v; e[i].u=id[u]; e[i].v=id[v]; if(id[u]!=id[v]) e[i].w-=in[v]; } V=cnt; r=id[r]; } return 1; } int main() { int i,v,n,m,c,d,l1,l2,mon,ed,j; while(scanf("%d%d",&n,&m)&&(n||m)) { a[0]=-1,mk[0]=0;//开始一直错把a0赋为0 这样mk1就错了 v=0,ed=0;//记点数和边数 for(i=1;i<=n;i++) { scanf("%d",&a[i]); mk[i]=mk[i-1]+a[i-1]+1; v+=a[i]+1; } for(i=1;i<=n;i++) { e[ed].u=0; e[ed].v=mk[i]+1; e[ed++].w=0; for(j=1;j<=a[i];j++)//保证高等级可以连向低等级 { e[ed].u=mk[i]+j+1; e[ed].v=mk[i]+j; e[ed++].w=0; } } for(i=0;i<m;i++) { scanf("%d%d%d%d%d",&c,&l1,&d,&l2,&mon); e[ed].u=mk[c]+l1+1; e[ed].v=mk[d]+l2+1; e[ed++].w=mon; } if(zhuliu(0,v+1,ed)==1)//加上根节点0 printf("%d\n",ans); else printf("-1\n"); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。