COGS
  • 图论工具
  • 演草纸
  • 帮助
  • 登录



    • 注册
    • 忘记密码
题目编号 用户编号
Gravatar
终焉折枝
积分：1649
提交：219 / 388

Pro461  [网络流24题] 餐巾 题解

更好的阅读体验：https://www.cnblogs.com/To-Carpe-Diem/p/19619769


大意

一个餐厅在相继的 $N$ 天里，每天需用的餐巾数不尽相同。假设第 $i$ 天需要 $r_i$ 块餐巾（$i = 1, 2, \dots, N$）。餐厅可以购买新的餐巾，每块餐巾的费用为 $p$ 分；或者把旧餐巾送到快洗部，洗一块需 $m$ 天，其费用为 $f$ 分；或者送到慢洗部，洗一块需 $n$ 天（$n \gt m$），其费用为 $s$ 分（$s \lt f$）。每天结束时，餐厅必须决定将多少块脏的餐巾送到快洗部，多少块餐巾送到慢洗部，以及多少块保存起来延期送洗。但是每天洗好的餐巾和购买的新餐巾数之和，要满足当天的需求量。


思路

一道很好的费用流题目，我们做一下考虑。

最终，由于每天都需要 $r_i$ 块餐巾布，那么最终我们的最大流一定是 $\sum r_i$，但是由于题目中的条件导致我们一定能求出最大流为 $\sum r_i$，主要的问题是费用最小，考虑如何建模。

首先每天我们首先要要求在这天开始的时候，有 $r_i$ 块新餐巾，而经过使用，这些餐巾在这天结束的时候会变成脏餐巾，那么我们考虑拆点，将一天分为 $in$ 和 $out$，$in$ 表示每天开始的时候，$out$ 表示每天结束的时候。

首先，我们需要向 $i_{out}$ 注入脏餐巾，我们建立源点 $S$，用来产生脏餐巾，容量为 $r_i$，花费为 $0$，其次我们建立汇点 $T$ 用来接收干净的餐巾，那么由 $i_{in}$ 向 $T$ 连容量为 $r_i$ 花费为 $0$ 的边。这样一来，如果最大流跑不满，就说明不可行。

接下来考虑题目中的约束，为了使得每天的 $i_{out} \to T$ 的流量流满，其实就是满足题目中的每天买餐巾的需求，我们可以从源点 $S$ 向每个 $i_{in}$ 连容量为 $\infty$，花费为 $p$ 的边。

接下来是洗衣服的约束，我们只需要每天的 $i_{out} \to {(i + m)}_{in}$ 容量为 $\infty$，花费为 $f$ 的边，$i_{out} \to {(i + n)}_{in}$ 容量为 $\infty$，花费为 $s$ 的边。

这样一来，直接跑最小费用最大流即可。


代码 

#include<bits/stdc++.h>
using namespace std;

const int MAXN = 4005;
const int MAXM = 20005;
struct node{
    int u, v, nxt, c, w;
}e[MAXM * 2];

int S, T;
int tot, h[MAXN], d[MAXN], pre[MAXN];
bool vis[MAXN];

void init(){
    tot = 0;
    memset(h, -1, sizeof(h));
}

void add(int u, int v, int c, int w){
    e[tot] = {u, v, h[u], c, w};
    h[u] = tot ++;
    e[tot] = {v, u, h[v], 0, -w};
    h[v] = tot ++;
}

bool spfa(){
    memset(vis, 0, sizeof(vis));
    memset(d, 0x3f, sizeof(d));
    memset(pre, -1, sizeof(pre));
    queue<int> q;
    q.push(S);
    d[S] = 0;
    vis[S] = true;
    while(!q.empty()){
        int u = q.front();
        q.pop();
        vis[u] = false;
        for(int i = h[u];~i;i = e[i].nxt){
            int v = e[i].v;
            if(e[i].c > 0){
                if(d[v] > d[u] + e[i].w){
                    d[v] = d[u] + e[i].w;
                    pre[v] = i;
                    if(!vis[v]){
                        q.push(v);
                        vis[v] = true;
                    }
                }
            }
        }
    }
    return (d[T] != 0x3f3f3f3f);
}

long long EK(){
    long long res = 0;
    while(spfa()){
        long long Min = 1e9;
        for(int i = T;i != S;i = e[pre[i]].u){
            Min = min(Min, (long long)e[pre[i]].c);
        }
        for(int i = T;i != S;i = e[pre[i]].u){
            e[pre[i]].c -= Min;
            e[pre[i] ^ 1].c += Min;
            res += e[pre[i]].w * Min;
        }
    }
    return res;
}

int N;
int a[MAXN];
int p, m, f, n, s;


int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
//    freopen("repair.in", "r", stdin);
//    freopen("repair.out", "w", stdout);
    cin >> N;
    init();
    for(int i = 1;i <= N;i ++){
    	cin >> a[i];
	}
	S = 0, T = 2 * N + 1;
	cin >> p >> m >> f >> n >> s;
	for(int i = 1;i <= N;i ++){
		add(S, i + N, a[i], 0);
		add(S, i, 1e9, p);
		add(i, T, a[i], 0);
		if(i + 1 <= N){
			add(i + N, (i + 1) + N, 1e9, 0);
		}
		if(i + m <= N){
			add(i + N, (i + m), 1e9, f);
		}
		if(i + n <= N){
			add(i + N, (i + n), 1e9, s);
		}
	}
	cout << EK() << endl;
    return 0;
}


题目461  [网络流24题] 餐巾      4      评论
2026-02-26 11:52:05    
Gravatar
终焉折枝
积分：1649
提交：219 / 388

Pro1867  [国家集训队2011]旅游 题解

更好的阅读体验：https://www.cnblogs.com/To-Carpe-Diem/p/19623719


大意

树上修改，路径和，路径最值，路径取反。


思路

基础树剖 + 线段树维护。


代码 


#include<iostream>
#include<algorithm>
#include<string>
using namespace std;

#define lc u << 1
#define rc u << 1 | 1
const int MAXN = 2 * 1e5 + 5;
const int INF = 1e9;
int sz[MAXN], top[MAXN], dep[MAXN];
int fa[MAXN], son[MAXN], dfn[MAXN], stk;
int nw[MAXN], n, val[MAXN];
int u_in[MAXN], v_in[MAXN], w_in[MAXN];

struct node{
	int to, nxt, len;
}e[MAXN << 1];
int tot = 0, h[MAXN];

void add(int u, int v, int w){
	e[++ tot] = {v, h[u], w};
	h[u] = tot;
}

void dfs1(int u, int f, int w){
	sz[u] = 1;
	fa[u] = f;
	dep[u] = dep[f] + 1;
	val[u] = w;
	son[u] = 0;
	for(int i = h[u];i;i = e[i].nxt){
		int v = e[i].to;
		if(v == f) continue;
		dfs1(v, u, e[i].len);
		sz[u] += sz[v];
		if(sz[v] > sz[son[u]]){
			son[u] = v;
		}
	}
}

void dfs2(int u, int tp){
	top[u] = tp;
	dfn[u] = ++ stk;
	nw[stk] = val[u];
	if(!son[u]) return;
	dfs2(son[u], tp);
	for(int i = h[u];i;i = e[i].nxt){
		int v = e[i].to;
		if(v == fa[u] || v == son[u]){
			continue;
		}
		dfs2(v, v);
	}
}

int sum[MAXN << 2];
int mx[MAXN << 2], mn[MAXN << 2];
bool lz[MAXN << 2];

void pushup(int u){
	sum[u] = sum[lc] + sum[rc];
	mx[u] = max(mx[lc], mx[rc]);
	mn[u] = min(mn[lc], mn[rc]);
}

void apply(int u){
	sum[u] = -sum[u];
	swap(mx[u], mn[u]);
	mx[u] = -mx[u];
	mn[u] = -mn[u];
	lz[u] = !lz[u];
}

void pushdown(int u){
	if(lz[u]){
		apply(lc);
		apply(rc);
		lz[u] = 0;
	}
}
void build(int u, int l, int r){
	if(l == r){
		if(l == 1){
			sum[u] = 0, mx[u] = -INF, mn[u] = INF;
		}
		else{
			sum[u] = mx[u] = mn[u] = nw[l];
		}
		return;
	}
	int mid = (l + r) >> 1;
	build(lc, l, mid);
	build(rc, mid + 1, r);
	pushup(u);
}

void p_modify(int u, int l, int r, int x, int v){
	if(l == r){
		sum[u] = mx[u] = mn[u] = v;
		lz[u] = false;
		return;
	}
	pushdown(u);
	int mid = (l + r) >> 1;
	if(x <= mid){
		p_modify(lc, l, mid, x, v);
	}
	else{
		p_modify(rc, mid + 1, r, x, v);
	}
	pushup(u);
}

void l_modify(int u, int l, int r, int L, int R){
	if(L <= l && r <= R){
		apply(u);
		return;
	}
	pushdown(u);
	int mid = (l + r) >> 1;
	if(L <= mid) l_modify(lc, l, mid, L, R);
	if(R > mid) l_modify(rc, mid + 1, r, L, R);
	pushup(u);
}

int ask_sum(int u, int l, int r, int L, int R){
	if(L <= l && r <= R){
		return sum[u];
	}
	pushdown(u);
	int ans = 0;
	int mid = (l + r) >> 1;
	if(L <= mid){
		ans += ask_sum(lc, l, mid, L, R);
	}
	if(R > mid){
		ans += ask_sum(rc, mid + 1, r, L, R);
	}
	return ans;
}

int ask_max(int u, int l, int r, int L, int R){
	if(L <= l && r <= R){
		return mx[u];
	}
	pushdown(u);
	int ans = -INF;
	int mid = (l + r) >> 1;
	if(L <= mid){
		ans = max(ask_max(lc, l, mid, L, R), ans);
	}
	if(R > mid){
		ans = max(ans, ask_max(rc, mid + 1, r, L, R));
	}
	return ans;
}

int ask_min(int u, int l, int r, int L, int R){
	if(L <= l && r <= R){
		return mn[u];
	}
	pushdown(u);
	int ans = INF;
	int mid = (l + r) >> 1;
	if(L <= mid){
		ans = min(ans, ask_min(lc, l, mid, L, R));
	}
	if(R > mid){
		ans = min(ans, ask_min(rc, mid + 1, r, L, R));
	}
	return ans;
}

void path_modify(int u, int v){
	while(top[u] != top[v]){
		if(dep[top[u]] < dep[top[v]]){
			swap(u, v);
		}
		l_modify(1, 1, n, dfn[top[u]], dfn[u]);
		u = fa[top[u]];
	}
	if(u == v) return;
	if(dep[u] > dep[v]) swap(u, v);
	l_modify(1, 1, n, dfn[u] + 1, dfn[v]);
}

int path_sum(int u, int v){
	int ans = 0;
	while(top[u] != top[v]){
		if(dep[top[u]] < dep[top[v]]){
			swap(u, v);
		}
		ans += ask_sum(1, 1, n, dfn[top[u]], dfn[u]);
		u = fa[top[u]];
	}
	if(u == v) return ans;
	if(dep[u] > dep[v]){
		swap(u, v);
	}
	ans += ask_sum(1, 1, n, dfn[u] + 1, dfn[v]);
	return ans;
}

int path_max(int u, int v){
	int ans = -INF;
	while(top[u] != top[v]){
		if(dep[top[u]] < dep[top[v]]){
			swap(u, v);
		}
		ans = max(ans, ask_max(1, 1, n, dfn[top[u]], dfn[u]));
		u = fa[top[u]];
	}
	if(u == v) return ans;
	if(dep[u] > dep[v]){
		swap(u, v);
	}
	ans = max(ans, ask_max(1, 1, n, dfn[u] + 1, dfn[v]));
	return ans;
}

int path_min(int u, int v){
	int ans = INF;
	while(top[u] != top[v]){
		if(dep[top[u]] < dep[top[v]]){
			swap(u, v);
		}
		ans = min(ans, ask_min(1, 1, n, dfn[top[u]], dfn[u]));
		u = fa[top[u]];
	}
	if(u == v) return ans;
	if(dep[u] > dep[v]){
		swap(u, v);
	}
	ans = min(ans, ask_min(1, 1, n, dfn[u] + 1, dfn[v]));
	return ans;
}

int main(){
    freopen("travel.in", "r", stdin);
    freopen("travel.out", "w", stdout);
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> n;
	for(int i = 1; i < n; i++){
		cin >> u_in[i] >> v_in[i] >> w_in[i];
		u_in[i]++; v_in[i]++;
		add(u_in[i], v_in[i], w_in[i]);
		add(v_in[i], u_in[i], w_in[i]);
	}
	dfs1(1, 0, 0);
	dfs2(1, 1);
	build(1, 1, n);
	int m; cin >> m;
	while(m--){
		string op; cin >> op;
		int x, y; cin >> x >> y;
		if(op == "C"){
			int target = dep[u_in[x]] > dep[v_in[x]] ? u_in[x] : v_in[x];
			p_modify(1, 1, n, dfn[target], y);
		} else {
			x++; y++;
			if(op == "N") path_modify(x, y);
			else if(op == "SUM") cout << path_sum(x, y) << "\n";
			else if(op == "MAX") cout << path_max(x, y) << "\n";
			else if(op == "MIN") cout << path_min(x, y) << "\n";
		}
	}
	return 0;
}



题目1867  [国家集训队2011]旅游      4      评论
2026-02-26 11:50:03    
Gravatar
终焉折枝
积分：1649
提交：219 / 388

Pro1689  [HNOI 2010] 弹飞绵羊 题解

更好的阅读体验：https://www.cnblogs.com/To-Carpe-Diem/p/19626422


大意

维护一个包含 $n$ 个弹力装置的数组，每个装置 $i$ 有弹力系数 $k_i$，绵羊从 $i$ 出发会弹到 $i + k_i$ 的位置，超出范围则弹飞。需要处理两种操作：查询从指定装置出发被弹飞的次数，以及修改指定装置的弹力系数


思路

如果说，从当前节点 $i$ 向节点 $i + k_i$ 连一条边，那么最终我们把跳出去的部分，设为 $n + 1$ 节点，那么我们就得到了一颗以 $n + 1$ 为根的树，每次我们要统计的就是 $i$ 到根的路径上的所有点之和。

但是由于这个东西需要动态的修改和查询，我们就可以用 $\text{LCT}$ 解决这个问题。

由于根节点是固定的，所以我们就不需要很多其他的奇妙操作了，只需要 splay 和 access 即可。

在查询的时候，只需要把 $x$ access 后 splay 到根即可，答案就是左子树大小，修改同理。


代码 

#include<iostream>
#include<vector>
using namespace std;

#define lc(x) t[x].ch[0]
#define rc(x) t[x].ch[1]
#define fa(x) t[x].fa

const int MAXN = 2 * 1e5 + 5;
vector<int> G[MAXN];
struct node{
	int ch[2], sz, fa;
}t[MAXN];

bool isroot(int x){
	return lc(fa(x)) != x && rc(fa(x)) != x;
}

void pushup(int x){
	t[x].sz = t[lc(x)].sz + t[rc(x)].sz + 1;
}

void rotate(int x){
	int y = fa(x), z = fa(y);
	int k = (rc(y) == x);
	if(!isroot(y)){
		t[z].ch[rc(z) == y] = x;
	}
	fa(x) = z;
	t[y].ch[k] = t[x].ch[k ^ 1];
	if(t[x].ch[k ^ 1]){
		fa(t[x].ch[k ^ 1]) = y;
	}
	t[x].ch[k ^ 1] = y;
	fa(y) = x;
	pushup(y);
	pushup(x);
}

void splay(int x){
	while(!isroot(x)){
		int y = fa(x), z = fa(y);
		if(!isroot(y)){
			(rc(y) == x) ^ (rc(z) == y) ? rotate(x) : rotate(y);
		}
		rotate(x);
	}
}

void access(int x){
	for(int y = 0;x;y = x, x = fa(x)){
		splay(x);
		rc(x) = y;
		pushup(x);
	}
}

int n, m, k[MAXN];

int main(){
	
	cin >> n;
	for(int i = 1;i <= n;i ++){
		cin >> k[i];
		t[i].sz = 1;
		fa(i) = (i + k[i]) > n ? n + 1 : (i + k[i]);
	}
	cin >> m;
	while(m --){
		int op, x, v; cin >> op >> x;
		x ++;
		if(op == 1){
			access(x);
			splay(x);
			cout << t[lc(x)].sz << '\n';
		}
		else{
			cin >> v;
			access(x);
			splay(x);
			lc(x) = fa(lc(x)) = 0;
			pushup(x);
			k[x] = v;
			fa(x) = x + v > n ? n + 1 : x + v;
		}
	}
	return 0;
}


题目1689  [HNOI 2010] 弹飞绵羊      4      评论
2026-02-26 11:46:15    
Gravatar
终焉折枝
积分：1649
提交：219 / 388

Pro1799  [国家集训队2012]tree(伍一鸣) 题解

更好的阅读体验:https://www.cnblogs.com/To-Carpe-Diem/p/19626423


大意

动态维护树上的乘积和加和。


思路

直接 $\text{LCT}$ 维护即可，但是注意乘法和加法的混合的下传。


代码 

#include<iostream>
using namespace std;

#define uint unsigned int
#define lc(x) t[x].ch[0]
#define rc(x) t[x].ch[1]
#define fa(x) t[x].fa
const int MAXN = 1e5 + 5;
const int MOD = 51061;

struct node{
	int ch[2], fa;
	uint val, sum, sz, add, mul;
	bool tag;
	node(){
		ch[1] = ch[0] = fa = 0;
		val = sum = sz = add = 0;
		mul = 1;
		tag = false;
	}
}t[MAXN];

bool isroot(int x){
	return (lc(fa(x)) != x) && (rc(fa(x)) != x);
}

void pushup(int x){
	t[x].sz = t[lc(x)].sz + t[rc(x)].sz + 1;
	t[x].sum = (t[lc(x)].sum + t[rc(x)].sum + t[x].val) % MOD;
}

void update_rev(int x){
	if(!x) return;
	swap(lc(x), rc(x));
	t[x].tag ^= 1;
}

void apply(int x, uint md, uint ad){
	if(!x) return;
	t[x].val = (1LL * t[x].val * md + ad) % MOD;
	t[x].sum = (1LL * t[x].sum * md + 1LL * ad * t[x].sz) % MOD;
	t[x].mul = (1LL * t[x].mul * md) % MOD;
	t[x].add = (1LL * t[x].add * md + ad) % MOD;
}

void pushdown(int x){
	if(t[x].tag){
		update_rev(lc(x));
		update_rev(rc(x));
		t[x].tag = 0;
	}
	if(t[x].mul != 1 || t[x].add != 0){
		apply(lc(x), t[x].mul, t[x].add);
		apply(rc(x), t[x].mul, t[x].add);
		t[x].mul = 1, t[x].add = 0;
	}
}

void rotate(int x){
	int y = fa(x), z = fa(y);
	int k = (rc(y) == x);
	if(!isroot(y)){
		t[z].ch[rc(z) == y] = x;
	}
	fa(x) = z;
	t[y].ch[k] = t[x].ch[k ^ 1];
	if(t[x].ch[k ^ 1]){
		fa(t[x].ch[k ^ 1]) = y;
	}
	t[x].ch[k ^ 1] = y;
	fa(y) = x;
	pushup(y);
	pushup(x);
}

void pushshell(int x){
	if(!isroot(x)){
		pushshell(fa(x));
	}
	pushdown(x);
}

void splay(int x){
	pushshell(x);
	while(!isroot(x)){
		int y = fa(x), z = fa(y);
		if(!isroot(y)){
			(rc(z) == y) ^ (rc(y) == x) ? rotate(x) : rotate(y);
		}
		rotate(x);
	}
}

void access(int x){
	for(int y = 0;x;y = x, x = fa(x)){
		splay(x);
		rc(x) = y;
		pushup(x);
	}
}

void makeroot(int x){
	access(x);
	splay(x);
	update_rev(x);
}

int findrt(int x){
	access(x);
	splay(x);
	while(lc(x)){
		pushdown(x);
		x = lc(x);
	}
	splay(x);
	return x;
}

void split(int x, int y){
	makeroot(x);
	access(y);
	splay(y);
}

void link(int x, int y){
	makeroot(x);
	if(findrt(y) != x) fa(x) = y;
}

void cut(int u1, int v1){
	split(u1, v1);
	if(lc(v1) == u1 && rc(u1) == 0){
		fa(u1) = lc(v1) = 0;
		pushup(v1);
	}
}

int main(){
	int n, q;
	cin >> n >> q;
	for(int i = 1;i <= n;i ++){
		t[i].val = t[i].sum = t[i].sz = 1;
		t[i].mul = 1;
	}
	for(int i = 1;i < n;i ++){
		int u, v; cin >> u >> v;
		link(u, v);
	}
	while(q --){
		char op; cin >> op;
		int u, v, u2, v2; uint c;
		if(op == '+'){
			cin >> u >> v >> c;
			split(u, v);
			apply(v, 1, c);
		}
		else if(op == '-'){
			cin >> u >> v >> u2 >> v2;
			cut(u, v);
			link(u2, v2);
		}
		else if(op == '*'){
			cin >> u >> v >> c;
			split(u, v);
			apply(v, c, 0);
		}
		else if(op == '/'){
			cin >> u >> v;
			split(u, v);
			cout << t[v].sum << endl;
		}
	}
	return 0;
}


题目1799  [国家集训队2012]tree(伍一鸣)      4      评论
2026-02-26 11:44:19    
Gravatar
终焉折枝
积分：1649
提交：219 / 388

Pro3609  [BZOJ 1101]Zap 题解

更好的阅读体验：https://www.cnblogs.com/To-Carpe-Diem/p/19631424


大意

给出 $a,b,d$，求满足 $1 \leq x \leq a$，$1 \leq y \leq b$，且 $\gcd(x,y)=d$ 的二元组 $(x,y)$ 的数量。


思路

也就是说，我们要统计的答案是 $\sum_{x = 1} ^ a \sum_{y = 1} ^ b [\gcd(x, y) = d]$。

我们考虑莫比乌斯反演。

我们令 $x = d \times x', y = d \times y'$，那么原式可化为 $\sum_{x' = 1} ^ {\lfloor \frac{x}{d} \rfloor} \sum_{y' = 1} ^ {\lfloor \frac{y}{d} \rfloor} [\gcd(x', y') = 1]$，我们再利用恒等式 $[\gcd(x, y) = 1] = \sum_{k | \gcd(x, y)} \mu(k)$ 代入，得到答案为 $\sum_{x' = 1} ^ {\lfloor \frac{x}{d} \rfloor} \sum_{y' = 1} ^ {\lfloor \frac{y}{d} \rfloor} \sum_{k | \gcd(x, y)} \mu(k)$，接下来，我们再改变一下，先枚举 $k$，再看那些情况符合的，答案就变为了 $\sum_{k = 1} ^ {\min(\lfloor \frac{x}{d} \rfloor, \lfloor \frac{y}{d} \rfloor)} \mu(k) \lfloor \frac{x}{d} \rfloor \lfloor \frac{y}{d} \rfloor$。


代码 

#include<bits/stdc++.h>
using namespace std;

const int MAXN = 50005;
int mu[MAXN], pr[MAXN];
bool vis[MAXN];
int sum[MAXN], tot = 0;

void init(int n){
	mu[1] = 1;
	for(int i = 2;i <= n;i ++){
		if(!vis[i]){
			pr[++ tot] = i;
			mu[i] = -1;
		}
		for(int j = 1;j <= tot && pr[j] * i <= n;j ++){
			vis[pr[j] * i] = 1;
			if(i % pr[j] == 0){
				mu[pr[j] * i] = 0;
				break;
			}
			mu[pr[j] * i] = -mu[i];
		}
	}
	for(int i = 1;i <= n;i ++){
		sum[i] = sum[i - 1] + mu[i];
	}
}

int solve(){
	int a, b, d, ans = 0;
	cin >> a >> b >> d;
	if(a > b) swap(a, b);
	a /= d, b /= d;
	for(int l = 1, r;l <= a;l = r + 1){
		r = min(a / (a / l), b / (b / l));
		ans += (sum[r] - sum[l - 1]) * (a / l) * (b / l);
	}
	return ans;
}

int main(){
	init(50000);
	int t; cin >> t;
	while(t --){
		cout << solve() << '\n';
	}
	return 0;
}


题目3609  [BZOJ 1101]Zap AAAAAAAAAAAAAAAAAAAA      4      评论
2026-02-26 11:40:44    
Gravatar
终焉折枝
积分：1649
提交：219 / 388

Pro3224  [NOI 2019]回家路线 题解

更好的阅读体验：https://www.cnblogs.com/To-Carpe-Diem/p/19640930


大意

从 $1$ 号点到第 $n$ 号点，每个地方是一个站点，有 $k$ 条路线，每个路线的车都有起始点和到达点，起始时间和到达时间，在等车的过程中他会哈气，问哈气值最小是什么？


思路

我们发现如果我们按时间进行排序，处理每个站点的航线的话，我们发现这样的话，后面的站点只能从前航线时间转移过来，那么这样的话我们做 DP 是没有后效性的，我们的转移是这样的，对于一个站点，若两条航线 $v_j = u_i$，那么有：$dp[i] = \min_{j \in \text{valid}} \{ dp[j] + A(p_i - q_j)^2 + B(p_i - q_j) + C \}$

我们不妨把这个转移式子拆开：$dp[i] = dp[j] + Ap_i^2 - 2Ap_iq_j + Aq_j^2 + Bp_i - Bq_j + C$

再把和 $i$ 与 $j$ 有关的项分开：$dp[i] = \underbrace{(dp[j] + Aq_j^2 - Bq_j)}_{\text{跟 } j \text{ 有关}} - \underbrace{2Ap_iq_j}_{i, j \text{ 混合}} + \underbrace{(Ap_i^2 + Bp_i + C)}_{\text{跟 } i \text{ 有关}}$

我们发现其实是可以做斜率优化的，我们将其化为 $y = kx + b$ 的形式：$\underbrace{dp[j] + Aq_j^2 - Bq_j}_{y} = \underbrace{(2Ap_i)}_{k} \cdot \underbrace{q_j}_{x} + \underbrace{(dp[i] - Ap_i^2 - Bp_i - C)}_{b}$

接下来维护一个下凸壳即可，由于是静态的，我们可以考虑直接用单调队列维护，但是有个很大的问题是，这些站点的东西要混起来吗？？？那怎么能知道哪个站点的能转移的点在哪呢？很简单的方式就是，我们直接维护 $n$ 个单调队列即可。每次对于每个站点进行转移即可。


代码 


#include<iostream>
#include<queue>
#include<algorithm> 
using namespace std;

#define ll long long
const int MAXN = 2 * 1e5 + 5;
int n, m;
ll A, B, C;
ll u[MAXN], v[MAXN], q[MAXN], p[MAXN], dp[MAXN];
int id1[MAXN], id2[MAXN];
deque<int> Q[MAXN >> 1];

double X(int x){
    return q[x];
}
double Y(int x){
    return dp[x] + A * q[x] * q[x] - B * q[x];
}
double slope(int a, int b){
    if(X(a) == X(b)) return Y(a) >= Y(b) ? 1e18 : -1e18;
    return (Y(a) - Y(b)) / (X(a) - X(b));
}
bool cmp1(int a, int b){
    return p[a] < p[b];
}
bool cmp2(int a, int b){
    return q[a] < q[b];
}


int main(){
    // freopen("rout.in", "r", stdin);
    // freopen("rout.out", "w", stdout);
    cin.tie(0) -> ios::sync_with_stdio(0);
    cin >> n >> m >> A >> B >> C;
    for(int i = 1;i <= m;i ++){
        cin >> u[i] >> v[i] >> p[i] >> q[i];
        id1[i] = id2[i] = i;
        dp[i] = 1e18;
    }
    sort(id1 + 1, id1 + m + 1, cmp1);
    sort(id2 + 1, id2 + m + 1, cmp2);
    dp[0] = q[0] = 0; v[0] = 1;
    Q[1].push_back(0);
    int nxt = 1;
    for(int k = 1;k <= m;k ++){
        int i = id1[k];
        while(nxt <= m && q[id2[nxt]] <= p[i]){
            int j = id2[nxt ++];
//            cout << j << '\n';
            if(dp[j] == 1e18) continue;
            int st = v[j];
            while(Q[st].size() > 1 && slope(j, Q[st][Q[st].size() - 2]) <= slope(Q[st][Q[st].size() - 2], Q[st][Q[st].size() - 1])){
                Q[st].pop_back();
            }
            Q[st].push_back(j);
        }
        int st = u[i];
        if(Q[st].empty()) continue;
        while(Q[st].size() > 1 && slope(Q[st][0], Q[st][1]) <= 2.0 * A * p[i]){
            Q[st].pop_front();
        }
		int j = Q[st][0];
//		cout << "i : " << i << ' ' << "j : " << j << '\n';
		dp[i] = dp[j] + A * (p[i] - q[j]) * (p[i] - q[j]) + B * (p[i] - q[j]) + C; 
    }
    ll ans = 1e18;
    for(int i = 1;i <= m;i ++){
        if(v[i] == n && dp[i] != 1e18){
            ans = min(dp[i] + q[i], ans);
        }
    }
    cout << ans << '\n';
    return 0;
}




题目3224  [NOI 2019]回家路线 AAAAAAAAAAAAAAAAAAAA      5      评论
2026-02-26 11:27:04    
中文繁體 中文简体

2026-02-28 07:09:26 以 Twitter Bootstrap 作为界面框架，应用 bootstrap 主题。 进程运行 0.024 s ，处理完成数据库 32 次。

由 CmYkRgB123 在线评测系统 强力驱动，版本 2.8.2.1 ，由 王者自由 二次开发。原作者 © BYVoid，保留部分权利。技术支持：河南省实验中学 邮箱：syxinxi@sina.cn