首页 > 其他分享 >2023牛客暑期多校训练营2 B Link with Railway Company

2023牛客暑期多校训练营2 B Link with Railway Company

时间:2024-03-08 22:11:34浏览次数:22  
标签:dep le return 10 int 多校 wson 牛客 Link

Problem Description

给你一个 \(n\) 个节点的树状铁路网络,维护一条边每天需要花费 \(c_i\) 代价。

现在有 \(m\) 条从 \(a_i\) 到 \(b_i\) ,每天的盈利为 \(x_i\) ,维护花费为 \(y_i\) 的路线可以运营。

你可以选择一部分路线运营,求每日的最大收益。

Input

第一行输入两个整数 \(n,m(2 \le n \le 10^4,1 \le m \le 10^4)\) 。

接下来 \(n-1\) 行每行输入三个整数 \(u_i,v_i,c_i(1 \le u_i,v_i \le n,1 \le c_i \le 10^5)\) ,表示 \(u_i,v_i\) 之间有一条维护花费为 \(c_i\) 的铁路 。

接下来 \(m\) 每行输入三个整数 \(a_i,b_i,x_i,y_i(1 \le a_i,b_i \le n,a_i \not= b_i,1 \le x_i,y_i \le 10^5)\) ,表示一条可运营的路线。

Output

输出每日的最大收益。

Solution

由于选择了一条线路之后,该线路内的所有边都需要维护,我们将路线视为一个权值为 \(x_i-y_i\) 的点 \(u_i\) , 边视为一个权值为 \(-c_i\) 的点 \(v_i\) ,可以很显然地发现这是一个最大权闭合子图的问题。

如此一来我们可以得到一个比较暴力的建图方式,那就是将源点 \(S\) 向每个 \(x_i-y_i > 0\) 的路线视为的点 \(u_i\) 连流量为 \(x_i-y_i\) 的边, 所有边视为的点 \(v_i\) 向汇点 \(T\) 连流量为 \(c_i\) 的边, \(u_i\) 向对应路径上的所有 \(v_i\) 连流量为 \(inf\) 的边,最后答案为 \(\sum\limits_{x_i-y_i>0}(x_i-y_i)-MaxFlow\)。

对于如何将边转成点,对于一条边我们可以将其深度较深的节点视为对应边的节点,这样一来每条边是有一一对应的节点的。而对于如何从路径对应的节点向边对应的节点连边,我们只需从 \(u_i\) 向除 \(lca(a_i,b_i)\) 以外的点 \(v_i\) 连边即可。

直接这样做流网络中的边数上界会达至 \(O(nm)\) 的级别,是无法通过此题的。但我们很显然地发现对于部分的 \(v_i\) 所构成的点集我们是可以重复利用的,又观察到该铁路网络是一棵树,那么我们便可以考虑采用树链剖分 \(+\) 线段树去优化建图。

我们先考虑对于一条路径在树剖后会被划分成 \(logn\) 条路径,再考虑对于线段树上一段 \(dfn\) 连续的路径会被划分成 \(logn\) 段,那么我们最终的边数就会变成 \(O(mlog^2n)\) 级别,而因为这个图是我们自己建的,数据其实并不能很好的卡掉,故配合上网络流的玄学复杂度我们可以跑过此题。

Code

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
constexpr int N = 1e5 + 10, M = 4e6 + 10, inf = 2e9;
struct Dinic {
	int n, S, T;
	int maxflow;
	int dep[N], cur[N];
	int head[N], e[M], flow[M], ne[M], idx;
	inline void init(int _n, int _S, int _T) {
		n = _n, S = _S, T = _T;
		idx = 0;
		for (int i = 0; i <= n; i++)head[i] = -1;
	}
	inline void addedge(int a, int b, int c) {
		e[idx] = b, flow[idx] = c, ne[idx] = head[a], head[a] = idx++;
		e[idx] = a, flow[idx] = 0, ne[idx] = head[b], head[b] = idx++;
	}
	bool bfs() {
		queue<int>q;
		memset(dep, -1, sizeof(int) * (n + 5));
		dep[S] = 0, q.push(S);
		while (!q.empty()) {
			int u = q.front();
			q.pop();
			for (int i = head[u]; i != -1; i = ne[i]) {
				int v = e[i];
				if (dep[v] == -1 && flow[i]) {
					dep[v] = dep[u] + 1;
					if (v == T)return true;
					q.push(v);
				}
			}
		}
		return false;
	}
	int dfs(int u, int limit) {
		if (u == T)return limit;
		int ret = 0;
		for (int i = cur[u]; i != -1 && ret < limit; cur[u] = i, i = ne[i]) {
			int v = e[i];
			if (dep[v] == dep[u] + 1 && flow[i]) {
				int d = dfs(v, min(limit - ret, flow[i]));
				if (d)ret += d, flow[i] -= d, flow[i ^ 1] += d;
				else dep[v] = -1;
			}
		}
		return ret;
	}
	int MaxFlow() {
		maxflow = 0;
		while (bfs()) {
			memcpy(cur, head, sizeof(int) * (n + 5));
			maxflow += dfs(S, inf);
		}
		return maxflow;
	}
};
struct Heavy_Light_Decomposition {
	int n;
	int dfn[N], seq[N], totdfn;
	int dep[N], siz[N], top[N], fa[N], wson[N];
	int head[N], e[M], w[M], ne[M], idx;
	inline void init(int _n) {
		totdfn = idx = 0, n = _n;
		for (int i = 0; i <= n; i++)head[i] = -1, wson[i] = 0;
	}
	inline void addedge(int a, int b, int c) {
		e[idx] = b, w[idx] = c, ne[idx] = head[a], head[a] = idx++;
	}
	void dfs1(int u, int father) {
		dep[u] = dep[father] + 1, fa[u] = father, siz[u] = 1;
		for (int i = head[u]; i != -1; i = ne[i]) {
			int v = e[i];
			if (v == father)continue;
			dfs1(v, u);
			siz[u] += siz[v];
			if (siz[v] > siz[wson[u]])wson[u] = v;
		}
	}
	void dfs2(int u, int chead) {
		dfn[u] = ++totdfn, top[u] = chead, seq[totdfn] = u;
		if (wson[u])dfs2(wson[u], chead);
		for (int i = head[u]; i != -1; i = ne[i]) {
			int v = e[i];
			if (v == fa[u] || v == wson[u])continue;
			dfs2(v, v);
		}
	}
	void work(int root) {
		dfs1(root, 0);
		dfs2(root, root);
	}
};
int n, m;
Dinic F;
Heavy_Light_Decomposition H;
void build(int u, int l, int r) {
	if (l == r) {
		F.addedge(u + n, H.seq[r], inf);
		return;
	}
	F.addedge(u + n, (u << 1) + n, inf);
	F.addedge(u + n, (u << 1 | 1) + n, inf);
	int mid = l + r >> 1;
	build(u << 1, l, mid);
	build(u << 1 | 1, mid + 1, r);
}
void SegAddedge(int u, int l, int r, int L, int R, int x) {
	if (L > r || R < l)return;
	if (L <= l && r <= R) {
		F.addedge(x, u + n, inf);
		return;
	}
	int mid = l + r >> 1;
	SegAddedge(u << 1, l, mid, L, R, x);
	SegAddedge(u << 1 | 1, mid + 1, r, L, R, x);
}
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m;
	F.init(5 * n + m + 10, 5 * n + m + 5, 5 * n + m + 6);
	H.init(n + 5);
	for (int i = 1; i <= n - 1; i++) {
		int u, v, c;
		cin >> u >> v >> c;
		H.addedge(u, v, c), H.addedge(v, u, c);
	}
	H.work(1);
	build(1, 1, n);
	for (int u = 1; u <= n; u++) {
		for (int i = H.head[u]; i != -1; i = H.ne[i]) {
			if (H.e[i] == H.fa[u])F.addedge(u, F.T, H.w[i]);
			//将边权等效转换为该边较深的节点且从负权点向汇点连边
		}
	}
	int ans = 0;
	for (int i = 1; i <= m; i++) {
		int u, v, x, y;
		cin >> u >> v >> x >> y;
		if (x <= y)continue;
		ans += x - y;
		F.addedge(F.S, i + 5 * n, x - y);//从源点向正权点连边
		while (H.top[u] != H.top[v]) {
			if (H.dep[H.top[u]] < H.dep[H.top[v]])swap(u, v);
			SegAddedge(1, 1, n, H.dfn[H.top[u]], H.dfn[u], i + 5 * n);
			u = H.fa[H.top[u]];
		}
		if (H.dep[u] < H.dep[v])swap(u, v);
		SegAddedge(1, 1, n, H.dfn[v] + 1, H.dfn[u], i + 5 * n);
		// 注意此处需要dfn[v]需要加1,因为流网络中点存的是路径上的边集,如果没有加1,就意味着取了lca(u,v)到其父亲的边,与定义不符。
	}
	cout << ans - F.MaxFlow() << endl;
}

标签:dep,le,return,10,int,多校,wson,牛客,Link
From: https://www.cnblogs.com/w1ck/p/18061966

相关文章

  • MATLAB----遗传算法及Simulink延时模块实例
    clctic%%参数初始化maxgen=100;%进化代数,即迭代次数,初始预定值选为100sizepop=200;%种群规模,初始预定值选为100pcross=0.9;%交叉概率选择,0和1之间,一般取0.9pmutation=0.01;%变异概率选择,0和1之间,一般取0.01individuals=struct('fitness',zeros(1,sizepop),'chrom',[]);%种群......
  • Flink CDC简介-flinkcdc-jian-jie
    FlinkCDC官方文档什么是FlinkCDC¶FlinkCDCConnectors是ApacheFlink的一组源连接器,使用变更数据捕获(CDC)从不同数据库中获取变更。FlinkCDCConnectors集成Debezium作为捕获数据变化的引擎。所以它可以充分发挥Debezium的能力。详细了解Debezium是什么。支......
  • Flink CDC 写 StarRocks
    Flink版本:1.17.1CDC版本:2.3.0StarRocks版本:2.5.8前言最近需要实时同步几个Mysql表到StarRocks,薅出之前写的Demo代码,简单改造了一下,加了个配置文件,可以通过修改配置文件指定source、sink表,这样就不用讲表名什么的写死到代码里面。再利用flinksession模式,把一堆任......
  • flink 中的水位线(Watermark)
    水位线Watermark实时统计使用了flinksql程序,使用flink-TVF表值函数滚动窗口按分钟进行数据聚合操作,消费的kafka数据需要在规定的时间窗口内进行推送数据并消费计算,为了解决处理乱序事件或延迟数据引入了Watermark,用来设置延迟计算时间等待迟到的数据,但不能无限期的等下去,必......
  • 2024牛客寒假算法基础集训营3
    A-智乃与瞩目狸猫、幸运水母、月宫龙虾#include<bits/stdc++.h>usingnamespacestd;usingi32=int32_t;usingi64=longlong;usingi128=__int128;usingldb=longdouble;#defineinti64usingvi=vector<int>;usingpii=pair<int,int>;usingv......
  • flink总结
    基本概念介绍flink的基本处理流程读取数据(source)->各种算子计算处理数据(rdd)-->输出数据(sink)有界流和无界流如果是从文件有限数据的地方读取数据就是有界流,如果是接到kafka或者socket这种地方就是无界流。有状态和无状态算子计算的过程中,是否要保存中间结算结果......
  • 【学习笔记】 - 基础数据结构 :Link-Cut Tree(进阶篇)
    前言LCT没题写可以去写树剖和一些线段树合并的题练手LCT的概念原本的树剖是对树进行剖分,剖分为重边和轻边LCT则是对于树分为虚边和实边,特殊的,LCT可以没有虚边(例:银河英雄传说v2)单独被包含在一个实链里的点称作孤立点在树剖中,我们使用线段树/树状数组来维护重链在Link-Cut......
  • MATLAB基本使用及SIMULINK建模仿真实验
    这是我总结的操作方法:1) M脚本文件的编写1、新建M-file;2、输入指令;3、保存(注意:保存路径需要与工作路径一致) 2)在SIMULINK中创建系统模型的步骤1、新建一个空白的 模型窗口。2、在SIMULINK模块库浏览器中,将创建系统模型所需要的功能模块用鼠标拖放到新建的模型窗口中......
  • macOS m1芯片报错 java.lang.UnsatisfiedLinkError: no taos in java.library.path
    项目中有用到TDengine,MacOSm1芯片本地开发启动项目报错如下java.lang.UnsatisfiedLinkError:notaosinjava.library.path方案一(推荐)以上错误是因为java在连接TDengine数据库的时候没有找到本地函数库。本地安装一下TDengine,然后在/usr/local/lib/下就会有taos函数库。因此......
  • 使用 SPL 高效实现 Flink SLS Connector 下推
    作者:潘伟龙(豁朗)背景日志服务SLS是云原生观测与分析平台,为Log、Metric、Trace等数据提供大规模、低成本、实时的平台化服务,基于日志服务的便捷的数据接入能力,可以将系统日志、业务日志等接入SLS进行存储、分析;阿里云Flink是阿里云基于ApacheFlink构建的大数据分析平台......