「csp校内训练 2019-10-30」解题报告
T1、树
题目链接(逃)
(Description)：
现在有一棵树，共 (N) 个节点。
规定：根节点为 (1) 号节点，且每个节点有一个点权。
现在，有 (M) 个操作需要在树上完成，每次操作为下列三种之一：
(1 x a)：操作 (1)，将节点 (x) 点权增加 (a)。
(2 x a)：操作 (2)，将以节点 (x) 为根的子树中所有点的权值增加 (a)。
(3 x)：操作 (3)，查询节点 (x) 到根节点的路径中所有点的点权和。
对于 (100\%) 的数据：(N , M leq 10 ^ 5)。
保证所有输入数据绝对值不超过 (10 ^ 6)。
显然可以树剖。时间复杂度 (O(m log_2 n))。
(Solution)：
也可以把所有操作放在节点上，(dfs) 遍历，遍历到的时候修改，遍历完一棵子树后回溯；
单点改整个子树答案加 (a)，否则子树 (u) 里点 (v) 答案增加 (dep_v imes a - (dep_u - 1) imes a)。
时间复杂度 (O(m log_2 n))。
(Source)：
#include <cstdio>
#include <cstring>
#include <algorithm>
int in() {
int x = 0; char c = getchar(); bool f = 0;
while (c < '0' || c > '9')
f |= c == '-', c = getchar();
while (c >= '0' && c <= '9')
x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
return f ? -x : x;
}
template<typename T>inline void chk_min(T &_, T __) { _ = _ < __ ? _ : __; }
template<typename T>inline void chk_max(T &_, T __) { _ = _ > __ ? _ : __; }
const int N = 1e5 + 5;
struct edge {
int next, to;
} e[N << 1];
int ecnt = 1, head[N];
int n, m, w[N];
inline void add_edge(const int u, const int v) {
e[++ecnt] = (edge){head[u], v}, head[u] = ecnt;
e[++ecnt] = (edge){head[v], u}, head[v] = ecnt;
}
struct segment_tree {
long long sum[N << 2];
long long lazy[N << 2];
inline void push_up(const int p) {
sum[p] = sum[p << 1] + sum[p << 1 | 1];
}
inline void spread(const int p, const int tl, const int tr, const int mid) {
sum[p << 1] += lazy[p] * (mid - tl + 1);
sum[p << 1 | 1] += lazy[p] * (tr - mid);
lazy[p << 1] += lazy[p];
lazy[p << 1 | 1] += lazy[p];
lazy[p] = 0;
}
void modify(int l, int r, int k, int tl = 1, int tr = n, int p = 1) {
if (l <= tl && tr <= r) {
sum[p] += 1ll * k * (tr - tl + 1);
lazy[p] += k;
return ;
}
int mid = (tl + tr) >> 1;
if (lazy[p])
spread(p, tl, tr, mid);
if (mid >= l)
modify(l, r, k, tl, mid, p << 1);
if (mid < r)
modify(l, r, k, mid + 1, tr, p << 1 | 1);
push_up(p);
}
long long query(int l, int r, int tl = 1, int tr = n, int p = 1) {
if (l <= tl && tr <= r)
return sum[p];
int mid = (tl + tr) >> 1;
if (lazy[p])
spread(p, tl, tr, mid);
if (mid < l)
return query(l, r, mid + 1, tr, p << 1 | 1);
if (mid >= r)
return query(l, r, tl, mid, p << 1);
return query(l, r, tl, mid, p << 1) + query(l, r, mid + 1, tr, p << 1 | 1);
}
} T;
//heavy-light decomposition begin
int siz[N], hson[N], fa[N], fro[N], dfn[N];
void dfs1(const int u) {
siz[u] = 1;
for (int i = head[u]; i; i = e[i].next) {
int v = e[i].to;
if (v == fa[u])
continue;
fa[v] = u;
dfs1(v);
siz[u] += siz[v];
if (siz[v] > siz[hson[u]])
hson[u] = v;
}
}
void dfs2(const int u, const int tp) {
fro[u] = tp;
dfn[u] = ++dfn[0];
if (hson[u])
dfs2(hson[u], tp);
for (int i = head[u]; i; i = e[i].next)
if (e[i].to != fa[u] && e[i].to != hson[u])
dfs2(e[i].to, e[i].to);
}
//heavy-light decomposition end
long long query(int u) {
long long ret = 0;
while (u) {
ret += T.query(dfn[fro[u]], dfn[u]);
u = fa[fro[u]];
}
return ret;
}
int main() {
//freopen("in", "r", stdin);
freopen("tree.in", "r", stdin);
freopen("tree.out", "w", stdout);
n = in(), m = in();
for (int i = 1; i <= n; ++i)
w[i] = in();
for (int i = 1; i < n; ++i)
add_edge(in(), in());
dfs1(1), dfs2(1, 1);
for (int i = 1; i <= n; ++i)
T.modify(dfn[i], dfn[i], w[i]);
while (m--) {
int typ = in(), x = in(), a;
if (typ == 1) {
a = in();
T.modify(dfn[x], dfn[x], a);
} else if (typ == 2) {
a = in();
T.modify(dfn[x], dfn[x] + siz[x] - 1, a);
} else {
printf("%lld
", query(x));
}
}
return 0;
}
T2、图
题目链接(逃)
(Description)：
有一个无向图：共 (n) 个节点，编号分别为 (1)~(n)，同时有 (m) 条无向边。
不同于他研究的树，图中边和点都有各自的权值，第 (i) 条边的边权为 (w_i)，第 (i) 个点的点权为 (c_i)。
从点 (s) 经过若干条边到点 (t) 的花费定义为：两点之间经过边的边权之和，加上经过的所有点 (包括 (s) 和 (t)) 的点权的最大值。
现在 Makik 将给出 (k) 次询问，每次给出两个整数 (s,t)，询问从 (s) 到 (t) 的最小花费。
请设计算法帮助 Makik 快速求解答案。
注：图中可能有两点之间存在多条边的情况，但不存在自环。
(1 leq n leq 250, 1 leq m<=10000, 1 leq k leq 10000)；
(1 leq a, b, s, t leq n, 1 leq c, w leq 100000, s
e t)。
(Solution)：
把点按点权从小到大排序，枚举起点并加入图，跑单源最短路，只能走已经加入的点；
再将该点当作中间点 (x)，更新 (f_{u,v}) ((u,v) 之间的答案)：
(f_{u,v} = max { dis_{u,x} + dis{x,v} + c_x })，其中 ((u, x))，((x, v)) 必须在当前的图中可达。
时间复杂度 (O(n^3))。
(Source)： 时间复杂度
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
int in() {
int x = 0; char c = getchar(); bool f = 0;
while (c < '0' || c > '9')
f |= c == '-', c = getchar();
while (c >= '0' && c <= '9')
x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
return f ? -x : x;
}
template<typename T>inline void chk_min(T &_, T __) { _ = _ < __ ? _ : __; }
template<typename T>inline void chk_max(T &_, T __) { _ = _ > __ ? _ : __; }
const int N = 255, M = 1e4 + 5;
int n, m, k;
int c[N], id[N];
int dis[N][N], e[N][N], f[N][N];
bool ok[N];
inline bool cmp(const int &i, const int &j) {
return c[i] < c[j];
}
void dijkstra(const int s, int *d) {
static int vis[N];
d[s] = 0;
for (int i = 1, u; i < n; ++i) {
u = 0;
for (int v = 1; v <= n; ++v)
if (ok[v] && vis[v] != s && ~d[v] && (!~d[u] || d[u] > d[v]))
u = v;
if (!u)
break;
vis[u] = s;
for (int v = 1; v <= n; ++v)
if (ok[v] && ~e[u][v]) {
if (!~d[v])
d[v] = d[u] + e[u][v];
else
chk_min(d[v], d[u] + e[u][v]);
}
}
}
inline void init() {
memset(dis, -1, sizeof(dis));
memset(f, -1, sizeof(f));
memset(e, -1, sizeof(e));
}
int main() {
//freopen("in", "r", stdin);
freopen("roadtoll.in", "r", stdin);
freopen("roadtoll.out", "w", stdout);
init();
n = in(), m = in(), k = in();
for (int i = 1; i <= n; ++i)
c[i] = in(), id[i] = i;
for (int i = 1, u, v, w; i <= m; ++i) {
u = in(), v = in(), w = in();
if (!~e[u][v])
e[u][v] = w;
else
chk_min(e[u][v], w);
e[v][u] = e[u][v];
}
std::sort(id + 1, id + 1 + n, cmp);
for (int i = 1; i <= n; ++i) {
ok[id[i]] = 1, dijkstra(id[i], dis[id[i]]);
for (int j = 1; j <= n; ++j)
dis[j][id[i]] = dis[id[i]][j];
for (int u = 1; u <= n; ++u)
if (~dis[u][id[i]])
for (int v = u + 1; v <= n; ++v)
if (~dis[id[i]][v]) {
if (!~f[u][v])
f[u][v] = dis[u][id[i]] + dis[id[i]][v] + c[id[i]];
else
chk_min(f[u][v], dis[u][id[i]] + dis[id[i]][v] + c[id[i]]);
}
}
for (int u = 1; u <= n; ++u)
for (int v = u + 1; v <= n; ++v)
f[v][u] = f[u][v];
while (k--)
printf("%d
", f[in()][in()]);
return 0;
}
T3、地图
题目链接(逃)
(Description)：
Makik 有一张详细的城市地图,地图标注了 L 个景区,编号为 1~L。而景区与景区之间建有单向高速通道。
这天,Makik 要去逛景区,他可以任选一个景区开始一天行程,且只能通过单向高速通道进入其他景区。
至少要参观两个景区，游玩最后要回到起始景区。
如果 Makik 参观了第 (i) 个景区，会获得一个乐趣值 (F_i)。且参观过得景区不会再获得乐趣值。
对于第 (i) 条单向高速通道，需要消耗 (T_i) 的时间，能够从 (L1_i) 到达 (L2_i)。
为了简化问题，参观景区不需要花费时间，Makik 想要最终单位时间内获得的乐趣值最大。
请你写个程序，帮 Makik 计算一下他能得到的最大平均乐趣值。
(2 leq L leq 1000, 2 leq P leq 5000, 1 leq F_i leq 1000, 1 leq T_i leq 1000)。
(Solution)：
显然 (01) 分数规划，故二分 (迭代好像不好写)。
设二分出 (mid)，则 (mid) 可行当且仅当存在环满足：
[frac{sum f_i }{sum e_i} geq mid iff
sum f_i >= mid geq e_i iff
sum f_i - sum mid cdot e_i geq 0
]
判正环即可。
时间复杂度 (O(G(n,m) log_2 ans))，其中 (G(n,m)) 为判负环复杂度，可以认为是 (O(nm))。
(Source)：
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
typedef double db;
int in() {
int x = 0; char c = getchar(); bool f = 0;
while (c < '0' || c > '9')
f |= c == '-', c = getchar();
while (c >= '0' && c <= '9')
x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
return f ? -x : x;
}
template<typename T>inline void chk_min(T &_, T __) { _ = _ < __ ? _ : __; }
template<typename T>inline void chk_max(T &_, T __) { _ = _ > __ ? _ : __; }
const int N = 1e3 + 5;
const double eps = 1e-4;
struct edge {
int next, to;
double w;
} e[N * 5];
int ecnt = 1, head[N];
int f[N];
int n, m;
db d[N];
bool vis[N];
bool dfs(int u, db mid) {
if (vis[u])
return 1;
vis[u] = 1;
for (int i = head[u]; i; i = e[i].next) {
int v = e[i].to;
db w = f[v] - mid * e[i].w;
if (d[v] <= d[u] + w) {
d[v] = d[u] + w;
if (dfs(v, mid))
return 1;
}
}
vis[u] = 0;
return 0;
}
bool chk(db mid) {
for (int i = 1; i <= n; ++i)
d[i] = vis[i] = 0;
for (int i = 1; i <= n; ++i)
if (dfs(i, mid))
return 1;
//std::queue<int> q;
//static int tim[N];
//for (int i = 1; i <= n; ++i)
// q.push(i), tim[i] = vis[i] = 1, d[i] = 0;
//while (!q.empty()) {
// int u = q.front(); q.pop();
// vis[u] = 0;
// if (tim[u] > n)
// return 1;
// for (int i = head[u]; i; i = e[i].next) {
// int v = e[i].to;
// db w = f[v] - mid * e[i].w;
// if (d[v] <= d[u] + w) {
// d[v] = d[u] + w;
// if (!vis[v])
// q.push(v), vis[v] = 1, ++tim[v];
// }
// }
//}
return 0;
}
db binary_search(db l, db r) {
while (r - l > eps) {
db mid = (l + r) / 2;
if (chk(mid))
l = mid;
else
r = mid;
}
return l;
}
int main() {
//freopen("in", "r", stdin);
freopen("travel.in", "r", stdin);
freopen("travel.out", "w", stdout);
n = in(), m = in();
for (int i = 1; i <= n; ++i)
f[i] = in();
while (m--) {
int u = in(), v = in(), w = in();
e[++ecnt] = (edge){head[u], v, 1.0 * w}, head[u] = ecnt;
}
printf("%.2lf
", binary_search(0, 500));
return 0;
}