【题解】JZOJ6578 / 洛谷P5201[USACO2019Jan]Shortcut G

这篇具有很好参考价值的文章主要介绍了【题解】JZOJ6578 / 洛谷P5201[USACO2019Jan]Shortcut G。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

洛谷 P5201 [USACO19JAN] Shortcut G

题意

在一个带权无向连通图上,每个点有 a i a_i ai 只奶牛,奶牛会走最短路径到 1 1 1,如果有多条路径,选择字典序最小的,定义移动总时间为所有奶牛走到 1 1 1 的时间之和。你可以修建一条从任意一点到 1 1 1 的边权为 t t t 的边,奶牛只有在平时走到 1 1 1 的路上看到这条边才会走。求最多能减少多少移动总时间。

题解

题目保证了对于每个点都有唯一的路径走到 1 1 1,那么可以建出一棵树,根节点为 1 1 1

然后统计一下子树中奶牛数量总和,对于每个点尝试建时间为 t t t 的新边,可以 O ( 1 ) O(1) O(1) 求出减少的移动总时间。设 j j j i i i 的子树中的节点,则减少的时间为 ( d i s i − t ) ∑ j a j (dis_i-t)\sum\limits_{j}a_j (disit)jaj

时间复杂度 O ( n ) O(n) O(n)文章来源地址https://www.toymoban.com/news/detail-670595.html

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 50005;
int n, m, t, a[N], vis[N];
LL dis[N], cnt[N], ans = 0;
int cn1 = 0, fi1[N], nx1[N << 1], to1[N << 1], va1[N << 1], cn2 = 0, fi2[N], nx2[N << 1], to2[N << 1];
void ad1(int u, int v, int w) {
	cn1++, nx1[cn1] = fi1[u], fi1[u] = cn1, to1[cn1] = v, va1[cn1] = w; 
	cn1++, nx1[cn1] = fi1[v], fi1[v] = cn1, to1[cn1] = u, va1[cn1] = w;
}
void ad2(int u, int v) { cn2++, nx2[cn2] = fi2[u], fi2[u] = cn2, to2[cn2] = v; }
struct node {
	int r;
	LL dis;
	bool operator < (const node &T) const { return dis > T.dis; }
};
priority_queue<node> pq;
void dij(int r) {
	memset(dis, 0x3f, sizeof(dis)), dis[r] = 0;
	pq.push((node){r, 0});
	while (!pq.empty()) {
		node h = pq.top();
		pq.pop();
		if (vis[h.r]) continue;
		vis[h.r] = 1;
		for (int i = fi1[h.r]; i; i = nx1[i])
			if (dis[to1[i]] > dis[h.r] + va1[i])
				dis[to1[i]] = dis[h.r] + va1[i], pq.push((node){to1[i], dis[to1[i]]});
	}
}
void dfs(int r) {
	cnt[r] = a[r];
	for (int i = fi2[r]; i; i = nx2[i]) dfs(to2[i]);
	for (int i = fi2[r]; i; i = nx2[i]) cnt[r] += cnt[to2[i]];
	if (t < dis[r]) ans = max(ans, (dis[r] - t) * cnt[r]);
}
int main() {
	scanf("%d%d%d", &n, &m, &t);
	for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
	for (int i = 1, u, v, w; i <= m; i++) scanf("%d%d%d", &u, &v, &w), ad1(u, v, w);
	dij(1);
	for (int i = 2; i <= n; i++) {
		int x = n;
		for (int j = fi1[i]; j; j = nx1[j])
			if (dis[i] == dis[to1[j]] + va1[j])
				x = min(x, to1[j]);
		ad2(x, i);
	}
	dfs(1);
	printf("%lld", ans);
	return 0;
}

到了这里,关于【题解】JZOJ6578 / 洛谷P5201[USACO2019Jan]Shortcut G的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【洛谷】P2690 [USACO04NOV] Apple Catching G(dp or 记忆化搜索)

    ACcode: 记忆化搜索: over~

    2024年02月15日
    浏览(33)
  • P2730 [USACO3.2] 魔板 Magic Squares 题解

    夜深人静的夜晚,我开了这道题。看起来,完成它是一件轻而易举的事。我想了想,打开Dev-C++,开始写代码。 然而,那时的我还不知道,我踏入了深渊...... 咳咳,中二病犯了,前面的文字请忽略。 题目要求最少操作次数,显然,我们要使用BFS来求解。 对于每个节点,接下

    2024年02月13日
    浏览(34)
  • 信息学奥赛一本通 1375:骑马修栅栏(fence) | 洛谷 P2731 [USACO3.3]骑马修栅栏 Riding the Fences

    ybt 1375:骑马修栅栏(fence) 洛谷 P2731 [USACO3.3]骑马修栅栏 Riding the Fences 1. 图论:欧拉回路 欧拉回路存在的条件:图中所有顶点的度都是偶数 欧拉路径存在的条件:图中只有两个度为奇数的顶点。而且这两个顶点是欧拉路径的起点与终点。 求解欧拉回路使用Hierholzer算法 复杂度

    2024年02月08日
    浏览(40)
  • [USACO11MAR] Brownie Slicing G题解(二分+二维前缀和+矩阵分割)

    题目地址 P3017 [USACO11MAR] Brownie Slicing G 二分最大化最小值 切割思路: 一行一行进行切割,如果这一行可以切割出b块大于等于mid的块,就开始切割下一行 如果无法切割出b块,就把正在切割的行与下一行拼起来一起切割 最后通过能切割出b块的水平块块够不够a条来判断m是否合

    2024年02月07日
    浏览(38)
  • 洛谷 P8742题解

    简单版(P2347)传送门 原题传送门 有一道 类似 的题目(P2347),先扯一扯~ 动态规划入门题(01背包 可行性问题 )~ 我们 设 (dp_j) 为能否用砝码称出 (j) 重量 ,1 为 可以 ,0 为 不可以 。 为了转移, (dp_{_{0}} gets 1) , 什么都不放时,重量为 0 ,因此可以称出。 那么 枚举

    2024年02月06日
    浏览(55)
  • 洛谷P1249题解

    一个正整数一般可以分为几个互不相同的自然数的和,如 3 = 1 + 2 3=1+2 3 = 1 + 2 , 4 = 1 + 3 4=1+3 4 = 1 + 3 , 5 = 1 + 4 = 2 + 3 5=1+4=2+3 5 = 1 + 4 = 2 + 3 , 6 = 1 + 5 = 2 + 4 6=1+5=2+4 6 = 1 + 5 = 2 + 4 。 现在你的任务是将指定的正整数 n n n 分解成若干个互不相同的自然数的和,且使这些自

    2024年02月05日
    浏览(52)
  • 洛谷 CF1743APassword 题解

    https://www.luogu.com.cn/problem/CF1743A 已知一个长度为四的,只包含字符 0 , 1 , 2 , … , 9 0,1,2,dots ,9 0 , 1 , 2 , … , 9 的字符串中不会出现哪些字符,求可能的字符串的数量。 Monocarp has forgotten the password to his mobile phone. The password consists of $ 4 $ digits from $ 0 $ to $ 9 $ (note that it can start wit

    2023年04月20日
    浏览(47)
  • 洛谷AT4888 题解-伦伦数

    A positive integer XX is said to be a lunlun number if and only if the following condition is satisfied: In the base ten representation of XX (without leading zeros), for every pair of two adjacent digits, the absolute difference of those digits is at most 11 . For example, 12341234 , 11 , and 334334 are lunlun numbers, while none of 3141531415 

    2024年02月06日
    浏览(52)
  • 洛谷 P1336 最佳课题选择 题解

    题目链接 状态:考虑 (f_{i,j}) 表示前 (i) 种论文里面,一共写了 (j) 篇,的最少花费时间。 转移策略:我们一次考虑每一种论文写多少篇。假设写 (k) 篇, (k in [0,j] cap mathbb{Z}) ,有转移方程: [f_{i,j} = min(f_{i-1,j-k} + text{cost}(i,k)), k in [0,j] cap mathbb{Z}] 其中 [text{

    2024年02月14日
    浏览(38)
  • 洛谷 P1122 最大子树和 题解

    一道入门的树形DP。 首先我们对于数据进行有序化处理,这便于我们利用数据结构特点(可排序性)来发觉数据性质(有序、单调、子问题等等性质),以便于后续的转化、推理和处理。 有序化可以“转化和创造”性质 首先将视角从无根树切换为有根树,这样我们就可以得

    2024年02月17日
    浏览(37)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包