首页 > 代码库 > hdu 4966 GGS-DDU 最小树形图
hdu 4966 GGS-DDU 最小树形图
来自九野~
给定n个技能，m个限制
下面是每个技能满级的级数
开始每个技能都是0级。
m个限制
(c,l1) (d,l2) cost
若c技能已经>=l1级，那么把点亮d技能 从0级一路点到l2级的花费是cost
。。他说的好有道理，我竟无言以对 _(:зゝ∠)_
最小树形图，用0做根，触发每个技能的0级花费是0
若已经点亮技能的x级，则点亮该技能的x-1级花费就是0
#include <stdio.h>#include <string.h>#include <iostream>#include <algorithm>#include <math.h>using namespace std;/** 最小树形图* 复杂度O(NM)* 点下标[0,n-1] 边下标[0,m-1]* 有向边表示：u->v 花费为cost* 返回最小树形图的边权和，-1表示不存在最小树形图*/const int INF = 100000000;const int MAXN = 1010; //点数const int MAXM = 1010000;//边数#define ll intstruct Edge{ int u,v; ll cost;}edge[MAXM]; int pre[MAXN],id[MAXN],visit[MAXN],edgenum;void add(int u, int v, ll cost){ Edge E = {u, v, cost}; edge[edgenum++] = E;}ll in[MAXN];ll zhuliu(int root,int n,int m,Edge edge[])//树根(注意是有向树，树根不能任意) 点数 边数 edge{ int u,v; ll res=0; while(1) { for(int i = 0;i < n;i++) in[i] = INF; for(int i = 0;i < m;i++) if(edge[i].u != edge[i].v && edge[i].cost < in[edge[i].v]) { pre[edge[i].v] = edge[i].u; in[edge[i].v] = edge[i].cost; } for(int i = 0;i < n;i++) if(i != root && in[i] == INF) return -1;//不存在最小树形图 int tn = 0; memset(id,-1,sizeof(id)); memset(visit,-1,sizeof(visit)); in[root] = 0; for(int i = 0;i < n;i++) { res += in[i]; v = i; while( visit[v] != i && id[v] == -1 && v != root) { visit[v] = i; v = pre[v]; } if( v != root && id[v] == -1 ) { for(int u = pre[v]; u != v ;u = pre[u]) id[u] = tn; id[v] = tn++; } } if(tn == 0)break;//没有有向环 for(int i = 0;i < n;i++) if(id[i] == -1) id[i] = tn++; for(int i = 0;i < m;) { v = edge[i].v; edge[i].u = id[edge[i].u]; edge[i].v = id[edge[i].v]; if(edge[i].u != edge[i].v) edge[i++].cost -= in[v]; else swap(edge[i],edge[--m]); } n = tn; root = id[root]; } return res; //-1为不存在最小树形图}void init(){ edgenum = 0;}#define N 55int n, m, a[N], sum[N];int Hash(int i, int j){ return sum[i-1]+j;}int main(){ int i, j, c, l1, d, l2, cost; while(scanf("%d %d",&n,&m), n+m){ init(); sum[0] = 0; for(i = 1; i <= n; i++)scanf("%d",&a[i]), a[i]++, sum[i] = sum[i-1]+a[i]; for(i = 1; i <= n; i++) add(0, Hash(i,1), 0); for(i = 1; i <= n; i++) for(j = 2; j <= a[i]; j++) add(Hash(i,j), Hash(i,j-1), 0); while(m--) { scanf("%d %d %d %d %d",&c, &l1, &d, &l2, &cost); l1++; l2++; add(Hash(c,l1), Hash(d,l2), cost); } printf("%d\n", zhuliu(0, sum[n]+1, edgenum, edge)); } return 0;}
hdu 4966 GGS-DDU 最小树形图
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。