[测试题]gentree

时间:2021-06-06 22:35:42

Description

给你一个有向连通图G,每点有个权值Di(0<Di),要求生成一棵树根为1号节点的有根树T。对于树中边E,E的代价为所有从根出发的且包含E的路径的终点权值的和。现求生成树T,使得边的代价总和最小。

Input

第一行N,M分别为点数,边数。(0<=N <= 20000;0<=M <= 200000)

接下来M行,每行两个数U,V描述边的两个端点,即从U到V有一条有向边。

最后一行N个数,顺次给出每个点的权值。

Output

一个数,最小代价。

Sample Input

5 4

1 2

1 3

3 4

3 5

1 2 3 4 5

Sample Output

23

Hint

样例解释:

如图只有一种生成树的方法,求得代价为23。[测试题]gentree

数据规模:

所有数据保证不会超过长整型(C++中的int)。

题解

归纳发现,算出的总代价就是每个节点在生成树中的深度$×$点权的和。

我们用贪心的思想,每个点的深度都要尽可能小。那么我们只需以$1$号节点为源点,跑一遍最短路即可。

由最小生成树的思想,我们易知所有求出的最短路径都在一棵生成树上,满足题意。

 #include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<ctime>
#include<cstdio>
#include<string>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=;
const int M=; int n,m,u,v;
struct tt
{
int to,next;
}edge[M+];
int path[N+],top;
int ans;
void Add(int u,int v); int dist[N+];
bool vis[N+];
void SPFA(); int main()
{
scanf("%d%d",&n,&m);
for (int i=;i<=m;i++)
{
scanf("%d%d",&u,&v);
Add(u,v);
}
SPFA();
for (int i=;i<=n;i++)
{
scanf("%d",&u);
ans+=u*dist[i];
}
printf("%d\n",ans);
return ;
} void Add(int u,int v)
{
edge[++top].to=v;
edge[top].next=path[u];
path[u]=top;
}
void SPFA()
{
memset(dist,/,sizeof(dist));
dist[]=;
vis[]=;
queue<int>Q;
Q.push();
while (!Q.empty())
{
for (int i=path[Q.front()];i;i=edge[i].next)
{
if (dist[edge[i].to]>dist[Q.front()]+)
{
dist[edge[i].to]=dist[Q.front()]+;
if (!vis[edge[i].to])
{
Q.push(edge[i].to);
vis[edge[i].to]=;
}
}
}
vis[Q.front()]=;
Q.pop();
}
}

[测试题]gentree的更多相关文章

  1. Android基础测试题&lpar;四&rpar;

    看了前两道题大家有没有发现,测试题少了(一),大家猜猜测试题(一)是什么? Android基础测试题(四): 需求: 建一个方法,格式化输出2016-11-14 10:15:26格式的当前时间,然后截 ...

  2. Android基础测试题(二)

    今天给大家带来的是Android基础测试题(二) 题目要求: 定义一个5位长度的整型数组并初始化,然后构建方法根据用户传入的数字判断是否存在数组中,如果存在,返回所在位置,如果不存在,返回-1 首先第 ...

  3. mysql测试题

    MySQL测试题 一.表关系 请创建如下表,并创建相关约束 创建数据库create database school charset utf8; 建表create table class(cid int ...

  4. 百度在线笔试编程测试题&lpar;Python&rpar;:整数分解成素数的积

    编程测试题: 输入一个正整数将其分解成素数的乘积,输入格式连续输入m个数,然后将这m个数分别分解,如 输入: 2 10 20 输出: 2 5 2 2 5 Python code: def primes ...

  5. ES6入门系列四(测试题分析)

    0.导言 ES6中新增了不少的新特性,来点测试题热热身.具体题目来源请看:http://perfectionkills.com/javascript-quiz-es6/. 以下将一题一题来解析what ...

  6. hadoop概述测试题和基础模版代码

    hadoop概述测试题和基础模版代码 1.Hadoop的创始人是DougCutting?() A.正确 B.错误答对了!正确答案:A解析:参考课程里的文档,这个就不解释了2.下列有关Hadoop的说法 ...

  7. C语言编写的随机产生四则运算测试题

    题目:编写一个四则运算测试题的程序,要求每道题都要随机产生 解题思路: 1.编写测试题,且为30道,就要用到循环函数,因此想到用for()函数 2.随机产生两个数,就想到用rand()函数. 注:1. ...

  8. 关于Linux测试题

    Linux 测试题: 1. 在Linux系统中,以 文件 方式访问设备 . 2. 某文件的权限为:drw-r--r--,用数值形式表示该权限,则该八进制数为: 644 ,该文件属性是 目录 . 3. ...

  9. linux测试题

    http://www.2cto.com/os/201307/225399.html  2013最新linux运维面试题 在对linux基本知识的归纳总结之后,这里是一份linux的测试题.希望能帮助大 ...

随机推荐

  1. 翻译:打造Edge渲染内核的浏览器

    最近开始了解UWP和Edge内核,在微软技术博客中找到一篇文章,主要是介绍Edge渲染内核使用技术.顺手翻译了一下.不对之处请斧正! Over the past several months, we ...

  2. oracle 12c中的隐含列

      Invisible Columns 使用select * from ,desc 等看不到该列, DROP TABLE tab1 PURGE; CREATE TABLE tab1 ( id NUMB ...

  3. sprintf溢出的bug

    向printf.sprintf这种函数在编译时很难检查错误,所以程序员必须小心.比如我就遇到了这样的bug: void test() { ]; sprintf(t,"); } //执行spr ...

  4. CSRF 攻击介绍

    CSRF是什么? CSRF(Cross-site request forgery),中文名称:跨站请求伪造,也被称为:one click attack/session riding,缩写为:CSRF/ ...

  5. Git-rebase与merge小结

    git merge是用来合并两个分支的. git merge b # 将b分支合并到当前分支 同样 git rebase b,也是把 b分支合并到当前分支 ---------------------- ...

  6. linux中的livecd、liveDVD和其他安装方式简介

    下载了几种不同格式的centos版本的iso文件,从而对比下各种iso文件的差别,下载的内容如下: 下载之后,分别在虚拟机中进行安装,从而查看有何区别: 1. 使用LiveCD进行安装 在选择安装介质 ...

  7. HDU 4062 Partition

    Partition Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Sub ...

  8. Andorid 刷新样式一

    一.Gradle中的Build.gradle依赖项目 compile 'com.github.moduth:blockcanary-android:1.1.0' debugCompile 'com.s ...

  9. linux云主机cpu一直很高降不下来,系统日志报nf&lowbar;conntrack&colon; table full&comma; dropping packet&period;

    在启用了iptables web服务器上,流量高的时候经常会出现下面的错误: ip_conntrack: table full, dropping packet 这个问题的原因是由于web服务器收到了 ...

  10. 跨浏览器的placeholder-jQuery版(jQuery插件EnPlaceholder)

    案例:整搜索框,需要默认占位符为"请输入关键词",获取焦点时,占位符消失或不可用(不影响正常输入),丢失焦点后,若用户无内容输入,占位符继续出现,继续占位.这种代码我想前端们已经很 ...