本文主要是介绍HDU多校第六场 1001 Salty Fish —— 最小割模型 + 启发式合并,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目链接:点我啊╭(╯^╰)╮
题目大意:
n n n 个点根为 1 1 1 的树,每个点上有价值 a i a_i ai 的苹果
树上有 m m m 个监控: x x x k k k c c c
在点 x x x 有一个监控,可以检测到最短距离在 k k k 以内的所有子树上的点
破坏该监控需要 c c c
求最大收获
解题思路:
说明一下几点:
对于每个监控,其最优的贪心策略是接受最远点的流量
每次合并将较短链上的儿子插入到长链
长链上的每个点都被插入一次,时间复杂度: O ( n ) O(n) O(n)
每条长链在链顶位置被插入一次,时间复杂度: O ( n ) O(n) O(n)
核心:最小割建模后,长链剖分优化合并
#include<bits/stdc++.h>
#define rint register int
#define deb(x) cerr<<#x<<" = "<<(x)<<'\n';
#define fi first
#define se second
using namespace std;
typedef long long ll;
using pii = pair <int,ll>;
const int maxn = 3e5 + 5;
int T, n, m, f[maxn], a[maxn], dep[maxn];
vector <pii> cam[maxn];
map <int, ll> mp[maxn];void merge(auto &mp1, auto &mp2){if(mp1.size() < mp2.size())mp1.swap(mp2);for(auto t : mp2) mp1[t.fi] += t.se;
}int main() {scanf("%d", &T);while(T--){scanf("%d%d", &n, &m);for(int i=1; i<=n; i++) mp[i].clear(), cam[i].clear();for(int i=2, x; i<=n; i++){scanf("%d", &x);f[i] = x;dep[i] = dep[x] + 1;}ll ans = 0;for(int i=1; i<=n; i++) scanf("%d", a+i), ans += a[i];for(int i=1; i<=m; i++){int x, k, c;scanf("%d%d%d", &x, &k, &c);cam[x].push_back({k, c});}for(int i=n; i; i--){mp[i][-dep[i]] += a[i];for(auto &u : cam[i]){auto it = mp[i].lower_bound(-dep[i] - u.fi);while(it != mp[i].end()) {if(it->se <= u.se){ans -= it->se;u.se -= it->se;it = mp[i].erase(it); // 下一个 } else {ans -= u.se;it->se -= u.se;u.se = 0;break;}}}if(f[i]) merge(mp[f[i]], mp[i]);}printf("%lld\n", ans);}
}
这篇关于HDU多校第六场 1001 Salty Fish —— 最小割模型 + 启发式合并的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!