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。
数据规模:
所有数据保证不会超过长整型(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的更多相关文章
-
Android基础测试题(四)
看了前两道题大家有没有发现,测试题少了(一),大家猜猜测试题(一)是什么? Android基础测试题(四): 需求: 建一个方法,格式化输出2016-11-14 10:15:26格式的当前时间,然后截 ...
-
Android基础测试题(二)
今天给大家带来的是Android基础测试题(二) 题目要求: 定义一个5位长度的整型数组并初始化,然后构建方法根据用户传入的数字判断是否存在数组中,如果存在,返回所在位置,如果不存在,返回-1 首先第 ...
-
mysql测试题
MySQL测试题 一.表关系 请创建如下表,并创建相关约束 创建数据库create database school charset utf8; 建表create table class(cid int ...
-
百度在线笔试编程测试题(Python):整数分解成素数的积
编程测试题: 输入一个正整数将其分解成素数的乘积,输入格式连续输入m个数,然后将这m个数分别分解,如 输入: 2 10 20 输出: 2 5 2 2 5 Python code: def primes ...
-
ES6入门系列四(测试题分析)
0.导言 ES6中新增了不少的新特性,来点测试题热热身.具体题目来源请看:http://perfectionkills.com/javascript-quiz-es6/. 以下将一题一题来解析what ...
-
hadoop概述测试题和基础模版代码
hadoop概述测试题和基础模版代码 1.Hadoop的创始人是DougCutting?() A.正确 B.错误答对了!正确答案:A解析:参考课程里的文档,这个就不解释了2.下列有关Hadoop的说法 ...
-
C语言编写的随机产生四则运算测试题
题目:编写一个四则运算测试题的程序,要求每道题都要随机产生 解题思路: 1.编写测试题,且为30道,就要用到循环函数,因此想到用for()函数 2.随机产生两个数,就想到用rand()函数. 注:1. ...
-
关于Linux测试题
Linux 测试题: 1. 在Linux系统中,以 文件 方式访问设备 . 2. 某文件的权限为:drw-r--r--,用数值形式表示该权限,则该八进制数为: 644 ,该文件属性是 目录 . 3. ...
-
linux测试题
http://www.2cto.com/os/201307/225399.html 2013最新linux运维面试题 在对linux基本知识的归纳总结之后,这里是一份linux的测试题.希望能帮助大 ...
随机推荐
-
翻译:打造Edge渲染内核的浏览器
最近开始了解UWP和Edge内核,在微软技术博客中找到一篇文章,主要是介绍Edge渲染内核使用技术.顺手翻译了一下.不对之处请斧正! Over the past several months, we ...
-
oracle 12c中的隐含列
Invisible Columns 使用select * from ,desc 等看不到该列, DROP TABLE tab1 PURGE; CREATE TABLE tab1 ( id NUMB ...
-
sprintf溢出的bug
向printf.sprintf这种函数在编译时很难检查错误,所以程序员必须小心.比如我就遇到了这样的bug: void test() { ]; sprintf(t,"); } //执行spr ...
-
CSRF 攻击介绍
CSRF是什么? CSRF(Cross-site request forgery),中文名称:跨站请求伪造,也被称为:one click attack/session riding,缩写为:CSRF/ ...
-
Git-rebase与merge小结
git merge是用来合并两个分支的. git merge b # 将b分支合并到当前分支 同样 git rebase b,也是把 b分支合并到当前分支 ---------------------- ...
-
linux中的livecd、liveDVD和其他安装方式简介
下载了几种不同格式的centos版本的iso文件,从而对比下各种iso文件的差别,下载的内容如下: 下载之后,分别在虚拟机中进行安装,从而查看有何区别: 1. 使用LiveCD进行安装 在选择安装介质 ...
-
HDU 4062 Partition
Partition Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Sub ...
-
Andorid 刷新样式一
一.Gradle中的Build.gradle依赖项目 compile 'com.github.moduth:blockcanary-android:1.1.0' debugCompile 'com.s ...
-
linux云主机cpu一直很高降不下来,系统日志报nf_conntrack: table full, dropping packet.
在启用了iptables web服务器上,流量高的时候经常会出现下面的错误: ip_conntrack: table full, dropping packet 这个问题的原因是由于web服务器收到了 ...
-
跨浏览器的placeholder-jQuery版(jQuery插件EnPlaceholder)
案例:整搜索框,需要默认占位符为"请输入关键词",获取焦点时,占位符消失或不可用(不影响正常输入),丢失焦点后,若用户无内容输入,占位符继续出现,继续占位.这种代码我想前端们已经很 ...