问题描述
圣诞节快到了, 蒜头君准备做一棵大圣诞树.
这棵树被表示成一组被编号的结点和一些边的集合, 树的结点从 1 到 n 编号, 树的根永远是 1. 每个结点都有一个自身特有的数值, 称为它的权重, 各个结点的权重可能不同. 对于一棵做完的树来说, 每条边都有一个价值 ve, 若设这条边 e 连接结点 i 和结点 j, 且 i 为 j 的父结点 (根是最老的祖先), 则该边的价值 ve=sj*we,sj 表示结点 j 的所有子孙及它自己的权重之和, we 表示边 e 的权值.
现在蒜头君想造一棵树, 他有 m 条边可以选择, 使得树上所有边的总价值最小, 并且所有的点都在树上, 因为蒜头君喜欢大树.
输入格式
第一行输入两个整数 n 和 m(0n,m50,000), 表示结点总数和可供选择的边数.
接下来输入一行, 输入 n 个整数, 依次表示每个结点的权重.
接下来输入 m 行, 每行输入 3 个正整数 a,b,c(1a,b,n,1c10,000), 表示结点 a 和结点 b 之间有一条权值为 c 的边可供造树选择.
输出格式
输出一行, 如果构造不出这样的树, 请输出 No Answer, 否则输出一个整数, 表示造树的最小价值.
样例输入
- 4 4
- 10 20 30 40
- 1 2 3
- 2 3 2
- 1 3 5
- 2 4 1
样例输出
370
其实这里就牵扯到最短路的一类问题, 这类问题看似是生成树问题但其实是最短路问题, 原因就在于边权的定义方式. 先来想一种简单的情况, 点的边权为 1, 或者说点没有边权, 对于 < i,j>(i 是 j 的父亲),ve=cntj*we(cnt 是 j 所在子树的结点个数), 我们可以用单源最短路算法求出所有结点到树根的最短路, 所有结点最短路之和就是答案. 为什么呢? 题目要求构造一棵树, 那么考虑从树根分别走到各个结点的路径长度之和, 则 < i,j > 的贡献就是 cntj*we, 因为每要走到 j 的子树中的一个点就要经过一次 < i,j>, 而这刚好是边权的定义. 那么如何最小化整棵树的边权之和呢? 其实就是最小化树根到每个结点的路径长度之和, 如果树根确定, 只需以树根为源点, 跑一遍单源最短路, 然后将各个结点的最短路累加起来, 如果树根不确定, 就需要对每个树根都求一遍到其他结点最短路之和, 取最小值. 回到原题, 每个结点都有权值, 其实也很好想, 每条边对于答案的贡献都扩大了, 比如某一结点的权值为 w, 先只考虑到这个点的路径, 都相当于由原来只经过一次变为经过 w 次, 也就是说, 可以把权值为 w 的点看成没有权值的 w 个在相同位置的点, 在统计答案时, 只需将 ans+=d[i] 修改为 ans+=w[i]*d[i].
- #include<cstdio>
- #include<cctype>
- #include<cstring>
- #include<queue>
- using namespace std;
- inline int get_num() { // 读入优化
- int num;
- char c;
- while((c=getchar())=='\n'||c==''||c=='\r');
- num=c-'0';
- while(isdigit(c=getchar())) num=num*10+c-'0';
- return num;
- }
- void put_num(int i) { // 输出优化
- if(i>9) put_num(i/10);
- putchar(i%10+'0');
- }
- const int maxn=5e4+5,maxm=1e5+5,inf=0x3f3f3f3f;
- int n,m,head[maxn],eid,d[maxn],vis[maxn],nw[maxn];
- long long ans; // 避免溢出
- struct edge { // 邻接表存储
- int v,w,next;
- edge(int v=0,int w=-1):v(v),w(w) {}
- } E[maxm];
- void init() { // 记得初始化
- memset(head,-1,sizeof(head));
- memset(d,inf,sizeof(d));
- }
- void insert(int u,int v,int w) {
- E[eid]=edge(v,w);
- E[eid].next=head[u];
- head[u]=eid++;
- }
- struct node { // 自定义结构体保存结点
- int n,s;
- node(int n,int s):n(n),s(s) {}
- bool operator <(const node& rhs) const { // 重载小于运算符, 使得最短路小的先出队
- return s>rhs.s;
- }
- };
- priority_queue<node> q;
- void dijkstra(int s) {
- d[s]=0;
- q.push(node(s,0));
- while(!q.empty()) {
- int u=q.top().n;
- q.pop();
- if(vis[u]) continue;
- vis[u]=1;
- for(int p=head[u];p+1;p=E[p].next) {
- int v=E[p].v;
- if(d[v]>d[u]+E[p].w) {
- d[v]=d[u]+E[p].w;
- q.push(node(v,d[v]));
- }
- }
- }
- }
- int main() {
- n=get_num();
- m=get_num();
- for(int i=1;i<=n;++i) nw[i]=get_num();
- init();
- int a,b,c;
- for(int i=1;i<=m;++i) {
- a=get_num();
- b=get_num();
- c=get_num();
- insert(a,b,c); // 注意插入的应是双向边
- insert(b,a,c);
- }
- dijkstra(1);
- for(int i=1;i<=n;++i) {
- if(d[i]==inf) {
- printf("No Answer");
- return 0;
- }
- ans+=nw[i]*d[i];
- }
- printf("%lld",ans);
- return 0;
- }
AC 代码
来源: http://www.bubuko.com/infodetail-2737074.html