2016 ACM/ICPC亚洲区沈阳站
2024-09-08 11:41:58
| A | B | C | D | E | F | G | H | I | J | K | L | M |
| O | O | O | $\varnothing$ | $\varnothing$ | $\varnothing$ | $\varnothing$ | $\varnothing$ | $\varnothing$ | $\varnothing$ |
签到。
签到
$$f[i] = f[i - 1] + 2 * f[i - 2] + i ^ 4$$
$$
\left[
\begin{matrix}
1 & 2 & 1 & 0 & 0 & 0 & 0 \\
1 & 0 & 0 & 0 & 0 & 0 & 0\\
0 &0 & 1 & 4 & 6 &4 & 1 \\
0 & 0 & 0 & 1 & 3 & 3 & 1 \\
0 & 0 & 0 & 0 & 1 & 2 & 1 \\
0 & 0 & 0 & 0 & 0 & 1 & 1 \\
0 & 0 & 0 & 0 & 0 & 0 & 1
\end{matrix}
\right]
\times
\left[
\begin{matrix}
f_{i-1} & 0 & 0 & 0 & 0 & 0 & 0 \\
f_{i-2} & 0 & 0 & 0 & 0 & 0 & 0\\
i^4 &0 & 0 & 0& 0 &0 & 0 \\
i^3 & 0 & 0 & 0 & 0 & 0 & 0 \\
i^2 & 0 & 0 & 0 & 0 & 0 & 0\\
i & 0 & 0 & 0 & 0 & 0 & 0 \\
1 & 0 & 0 & 0 & 0 & 0 & 0
\end{matrix}
\right]=
\left[
\begin{matrix}
f_{i} & 0 & 0 & 0 & 0 & 0 & 0 \\
f_{i} & 0 & 0 & 0 & 0 & 0 & 0\\
(i+1)^4 &0 & 0 & 0& 0 &0 & 0 \\
(i+1)^3 & 0 & 0 & 0 & 0 & 0 & 0 \\
(i+1)^2 & 0 & 0 & 0 & 0 & 0 & 0\\
i+1 & 0 & 0 & 0 & 0 & 0 & 0 \\
1 & 0 & 0 & 0 & 0 & 0 & 0
\end{matrix}
\right]
$$
#include <bits/stdc++.h>
#define ll long long const ll MOD = ;
const int N = ; struct Mat {
ll a[][];
Mat() {
memset(a, , sizeof(a));
}
Mat(int x) {
memset(a, , sizeof(a));
for (int i = ; i <= N; i++)
a[i][i] = ;
}
Mat operator * (const Mat &rhs) const {
Mat c;
for (int i = ; i <= N; i++)
for (int j = ; j <= N; j++)
for (int k = ; k <= N; k++)
c.a[i][j] = (c.a[i][j] + a[i][k] * rhs.a[k][j] % MOD) % MOD;
return c;
}
}; Mat qp(Mat a, int b) {
Mat c();
while (b) {
if (b & ) c = a * c;
a = a * a;
b >>= ;
}
return c;
} int main() {
int T;
scanf("%d", &T);
Mat base;
base.a[][] = ; base.a[][] = ; base.a[][] = ;
base.a[][] = ;
base.a[][] = ; base.a[][] = ; base.a[][] = ; base.a[][] = ; base.a[][] = ;
base.a[][] = ; base.a[][] = ; base.a[][] = ; base.a[][] = ;
base.a[][] = ; base.a[][] = ; base.a[][] = ;
base.a[][] = ; base.a[][] = ;
base.a[][] = ;
while (T--) {
int n, a, b;
scanf("%d%d%d", &n, &a, &b);
if (n == ) {
printf("%d\n", a);
continue;
}
if (n == ) {
printf("%d\n", b);
continue;
}
n--;
n--;
Mat ans;
ans.a[][] = b; ans.a[][] = a; ans.a[][] = ; ans.a[][] = ; ans.a[][] = ; ans.a[][] = ; ans.a[][] = ;
ans = qp(base, n) * ans;
printf("%lld\n", ans.a[][] % MOD);
}
return ;
}
博弈。
$dp[n][a][b]$ 表示当前剩下 $n$ 个物品，第一个人有 $a$ 元钱，第二个人有 $b$ 元钱，第一个人能获得的物品数。
$dp[1][a][b] = [a\leq b]$
消除奇偶性可以通过从 $dp[i - 1][b][a]$ 转移过来。这样就不用考虑奇偶了。
然后枚举两个人分别要出多少钱，当第一个人出 $x$ 块钱，第二个人出 $x+1$ 块钱会使第一个人的收益变小，那么第二个人会继续加价。同理第一个人会继续加价。当无法得到更好的收益的时候就停下来。
#include <cstdio>
#include <algorithm>
#include <cstring> const int N = ;
short dp[N][N][N]; int n, T, a, b; inline int geta(int n, int a) {
return n / * a + (n - n / ) * (a + );
} int main() {
for (int a = ; a < N; a++)
for (int b = ; b < N; b++)
if (a >= b) dp[][a][b] = ;
for (int i = ; i < N; i++) {
for (int a = ; a < N; a++) {
int limit = std::min(N, geta(i, a));
for (int b = ; b < limit; b++) {
if (a == b) {
dp[i][a][b] = (i + ) / ;
continue;
}
int vala = i - dp[i - ][b][a];
int valb = ;
for (int u = ; ; u++) {
if (b < u || (valb = (i - - dp[i - ][b - u][a])) >= vala) {
dp[i][a][b] = vala;
break;
}
if (a < u || (vala = (i - dp[i - ][b][a - u])) <= valb) {
dp[i][a][b] = valb;
break;
}
}
}
}
}
scanf("%d", &T);
while (T--) {
scanf("%d%d%d", &n, &a, &b);
int ans1 = dp[n][a][b], ans2 = n - ans1;
printf("Alice %d Bob %d\n", ans1, ans2);
}
return ;
}
经过暑假牛客多校的洗礼，看到团就想到暴搜...
首先用了bfs+bitset。T了。
改成vector判，又T了。
看了一份题解是dfs，存团的是数组。
我把那份代码的数组改成vector，还是T。
这么卡STL的吗...
#include <bits/stdc++.h> const int N = ;
std::vector<int> G[N];
bool mp[N][N]; int ans, n, m, s; void solve(int *a, int u) {
if (a[] == s) {
ans++;
return;
}
for (int v: G[u]) {
if (v <= u) continue;
bool flag = ;
for (int j = ; j <= a[]; j++) {
if (!mp[a[j]][v]) {
flag = ;
break;
}
}
if (!flag) continue;
a[++a[]] = v;
solve(a, v);
--a[];
}
} int a[N]; int main() {
int T;
scanf("%d", &T);
while (T--) {
scanf("%d%d%d", &n, &m, &s);
for (int i = ; i <= n; i++) {
G[i].clear();
for (int j = ; j <= n; j++)
mp[i][j] = ;
a[i] = ;
}
for (int i = ; i < m; i++) {
int u, v;
scanf("%d%d", &u, &v);
if (u > v) std::swap(u, v);
G[u].push_back(v);
mp[u][v] = mp[v][u] = ;
}
ans = ;
for (int i = ; i <= n; i++) {
a[] = ;
a[] = i;
solve(a, i);
}
printf("%d\n", ans);
}
return ;
}
积分题。
看的这篇 https://www.cnblogs.com/chen9510/p/7635679.html
#include <bits/stdc++.h> const double pi = acos(-1.0);
const double eps = 1e-; inline int dcmp(double x) {
if (fabs(x) < eps) return ;
return x < ? - : ;
} double cal(double x) {
return sin(x) - x * cos(x) - / 3.0 * sin(x) * sin(x) * sin(x);
} double calV(double mid) {
double V = cal(acos(1.0)) - cal(acos(1.0 - mid));
V *= -2.0 / mid;
return V;
} double cal2(double x) {
return x + sin( * x) / ;
} double area(double a, double x) {
return (cal2(pi / 2.0) - cal2(asin(x / a))) * a;
} int main() {
int T;
scanf("%d", &T);
while (T--) {
double d;
scanf("%lf", &d);
if (dcmp(d - ) >= ) {
double h = - * d;
double a = sqrt( * + h * h) / ;
printf("%.5f\n", pi * a);
continue;
}
if (dcmp(d) == ) {
puts("0.00000");
continue;
}
double l = , r = 2.0;
for (int i = ; i < ; i++) {
double mid = (l + r) / 2.0;
double V = calV(mid);
if (dcmp(V - pi * d) == ) break;
if (dcmp(V - pi * d) < ) l = mid;
else r = mid;
}
double mid = l; int flag = ;
if (mid < ) flag = -;
double len = sqrt(mid * mid + );
double h = sqrt( - ( - mid) * ( - mid));
double a = len / ( + flag * sqrt( - h * h));
double x = a - len;
printf("%.5f\n", area(a, x));
}
}
先把AC自动机建出来。在AC自动机上DP。
$dp[i] = \sum \frac{1}{6} \times dp[from]$
$from$ 为能转到 $i$ 且不为某个串的结尾的结点
因为会存在环，所以高斯消元就行了。
#include <bits/stdc++.h> const int N = + ; double mat[N][N];
const double eps = 1e-; inline void gauss(int n) {
for(int i = ; i <= n; i++) {
int r = i;
for(int j = i + ; j <= n; j++)
if(std::fabs(mat[r][i]) < std::fabs(mat[j][i]))
r = j;
if(r != i) std::swap(mat[i], mat[r]);
for(int j = ; j <= n; j++) {
if(j == i) continue;
double t = mat[j][i] / mat[i][i];
for(int k = i; k <= n + ; k++)
mat[j][k] -= mat[i][k] * t;
}
}
for(int i = ; i <= n; i++) {
mat[i][n + ] /= mat[i][i];
}
} struct Aho {
static const int sz = ;
int ch[N][sz], last[N], fail[N], tol;
bool end[N];
void init() {
tol = ;
newnode();
}
inline int newnode() {
memset(ch[tol], , sizeof(ch[tol]));
last[tol] = fail[tol] = end[tol] = ;
return tol++;
}
void insert(int *a, int n) {
int u = ;
for (int i = ; i < n; i++) {
int id = a[i] - ;
if (!ch[u][id]) ch[u][id] = newnode();
u = ch[u][id];
}
end[u] = ;
}
void build() {
std::queue<int> que;
for (int i = ; i < sz; i++)
if (ch[][i]) que.push(ch[][i]), fail[ch[][i]] = last[ch[][i]] = ;
while (!que.empty()) {
int u = que.front(); que.pop();
end[u] |= end[last[u]];
for (int i = ; i < sz; i++) {
int &v = ch[u][i];
if (v) {
fail[v] = ch[fail[u]][i];
que.push(v);
last[v] = end[fail[v]] ? fail[v] : last[fail[v]];
} else {
v = ch[fail[u]][i];
}
}
}
}
void solve() {
memset(mat, , sizeof(mat));
mat[][tol] = -1.0;
for (int i = ; i < tol; i++) {
mat[i][i] = -1.0;
if (end[i]) continue;
for (int j = ; j < sz; j++)
mat[ch[i][j]][i] += 1.0 / ;
}
gauss(tol - );
bool flag = ;
for (int i = ; i < tol; i++)
if (end[i]) {
if (flag) putchar(' ');
printf("%.6f", mat[i][tol]);
flag = ;
}
puts("");
}
} ac; int a[]; int main() {
int T;
scanf("%d", &T);
for (; T--; ) {
int n, l;
scanf("%d%d", &n, &l);
ac.init();
for (int i = ; i <= n; i++) {
for (int j = ; j < l; j++)
scanf("%d", a + j);
ac.insert(a, l);
}
ac.build();
ac.solve();
}
return ;
}
$dp[u] = min(dp[anc] + (sum[u] - sum[anc])^2 + p)$
$anc$ 为 $u$ 到根的路径上的结点。
斜率优化DP一下。在进入一个结点时存储一下对当前队列的修改，离开一个结点时改回去，这样就能保证进入一个结点时，队列存储的都是它的祖先。
#include <bits/stdc++.h>
#define pii pair<int, int>
#define ll long long
#define fi first
#define se second const int N = 1e5 + ;
const double eps = 1e-;
ll dp[N];
int n, p, que[N], l, r;
ll sum[N];
std::vector<std::pii> G[N]; inline ll sqr(ll x) {
return x * x;
} inline ll up(int i, int j) {
return dp[i] + sqr(sum[i]) - dp[j] - sqr(sum[j]);
} inline ll down(int i, int j) {
return sum[i] - sum[j];
} ll ans; void dfs(int u, int fa = ) {
std::vector<std::pii> vec;
int x = l, y = r;
while (l < r && up(que[l + ], que[l]) <= down(que[l + ], que[l]) * * sum[u]) {
vec.push_back(std::pii(l, que[l]));
l++;
}
if (u != ) {
dp[u] = dp[que[l]] + sqr(sum[u] - sum[que[l]]) + p;
ans = std::max(ans, dp[u]);
}
while (l < r && up(que[r], que[r - ]) * down(u, que[r]) >= up(u, que[r]) * down(que[r], que[r - ])) {
vec.push_back(std::pii(r, que[r]));
r--;
}
que[++r] = u;
for (auto v: G[u]) {
if (v.fi == fa) continue;
sum[v.fi] = sum[u] + v.se;
dfs(v.fi, u);
}
l = x, r = y;
for (auto p: vec)
que[p.fi] = p.se;
} int main() {
int T;
scanf("%d", &T);
while (T--) {
scanf("%d%d", &n, &p);
for (int i = ; i <= n; i++)
dp[i] = sum[i] = , G[i].clear();
for (int i = , u, v, w; i < n; i++) {
scanf("%d%d%d", &u, &v, &w);
G[u].push_back(std::pii(v, w));
G[v].push_back(std::pii(u, w));
}
dp[] = -p;
que[l = r = ] = ;
ans = ;
dfs();
printf("%lld\n", ans);
}
return ;
}
基环树先找出环，用一个数组 $a$ 记录位置。然后以环上的每个点为根，去bfs非环上的点得到bfs序.
那么对于非环上的点，与他距离不大于 $k$ 的点bfs序连续，对于环上的点，与他距离不大于 $k$ 的点在 $a$ 数组里连续
这样就可以用线段树维护了。
然后就是恶心的细节了。
#include <bits/stdc++.h>
#define ll long long inline void checkmax(int &a, int b) {
if (a < b) a = b;
} inline void checkmin(int &a, int b) {
if (a > b) a = b;
} const int N = 1e5 + ;
std::vector<int> vec[N];
int fa[N], son[N], n, id[N], BCC[N], a[N];
int tol;
bool vis[N]; void getBCC(int u, int v) {
for (int i = u; i != v; i = fa[i])
a[BCC[i] = ++a[]] = i;
a[BCC[v] = ++a[]] = v;
} void dfs(int u, int pre) {
vis[u] = ;
for (int v: vec[u]) {
if (v == pre) continue;
if (!vis[v]) {
fa[v] = u;
dfs(v, u);
} else if (!BCC[u]) {
getBCC(u, v);
}
}
} int que[N];
int ls[N], rs[N], lg[N], rg[N]; void bfs(int s) {
int h = , t = ;
que[++t] = s;
id[s] = ++tol;
while (h != t) {
int u = que[++h]; ls[u] = tol + ;
for (int v: vec[u])
if (!id[v] && !BCC[v]) {
fa[v] = u;
que[++t] = v;
id[v] = ++tol;
}
rs[u] = tol;
}
for (int i = ; i <= t; i++) {
int u = que[i];
lg[u] = N; rg[u] = -N;
for (int v: vec[u])
if (id[v] > id[u] && !BCC[v])
checkmin(lg[u], ls[v]), checkmax(rg[u], rs[v]);
}
} struct Seg {
#define lp p << 1
#define rp p << 1 | 1
static const int NN = N * ;
ll sum[NN], lazy[NN];
void build(int p, int l, int r) {
sum[p] = lazy[p] = ;
if (l == r) return;
int mid = l + r >> ;
build(lp, l, mid);
build(rp, mid + , r);
}
inline void pushup(int p) {
sum[p] = sum[lp] + sum[rp];
}
inline void tag(int p, int len, ll w) {
lazy[p] += w;
sum[p] += len * w;
}
inline void pushdown(int p, int llen, int rlen) {
if (lazy[p]) {
tag(lp, llen, lazy[p]);
tag(rp, rlen, lazy[p]);
lazy[p] = ;
}
}
void update(int p, int l, int r, int x, int y, int w) {
if (x > r || l > y) return;
if (x <= l && y >= r) {
tag(p, r - l + , w);
return;
}
int mid = l + r >> ;
pushdown(p, mid - l + , r - mid);
if (x <= mid) update(lp, l, mid, x, y, w);
if (y > mid) update(rp, mid + , r, x, y, w);
pushup(p);
}
ll query(int p, int l, int r, int x, int y) {
if (x > r || l > y) return ;
if (x <= l && y >= r) return sum[p];
int mid = l + r >> ;
pushdown(p, mid - l + , r - mid);
ll ans = ;
if (x <= mid) ans += query(lp, l, mid, x, y);
if (y > mid) ans += query(rp, mid + , r, x, y);
return ans;
}
inline int getl(int x) { return (x > ) ? x - : a[]; }
inline int getr(int x) { return (x < a[]) ? x + : ; }
inline void update(int u, int w) { update(, , tol, u, u, w); }
inline ll query(int u) { return query(, , tol, u, u); }
void update(int u, int k, int w) {
update(id[u], w);
if (k >= ) {
update(, , tol, ls[u], rs[u], w);
if (!BCC[u]) update(id[fa[u]], w);
else {
update(id[a[getl(BCC[u])]], w);
update(id[a[getr(BCC[u])]], w);
}
}
if (k >= ) {
update(, , tol, lg[u], rg[u], w);
if (!BCC[u]) {
update(id[u], -w);
update(, , tol, ls[fa[u]], rs[fa[u]], w);
int p = BCC[fa[u]];
if (!p) update(id[fa[fa[u]]], w);
else update(id[a[getl(p)]], w), update(id[a[getr(p)]], w);
} else {
int bl = getl(BCC[u]), br = getr(BCC[u]);
update(, , tol, ls[a[bl]], rs[a[bl]], w);
update(, , tol, ls[a[br]], rs[a[br]], w);
if (getl(bl) != br) update(id[a[getl(bl)]], w);
if (getr(br) != bl && getr(br) != getl(bl)) update(id[a[getr(br)]], w);
}
}
}
ll query(int u, int k) {
ll ans = query(id[u]);
if (k >= ) {
ans += query(, , tol, ls[u], rs[u]);
if (!BCC[u]) ans += query(id[fa[u]]);
else ans += query(id[a[getl(BCC[u])]]) + query(id[a[getr(BCC[u])]]);
}
if (k >= ) {
ans += query(, , tol, lg[u], rg[u]);
if (!BCC[u]) {
ans += query(, , tol, ls[fa[u]], rs[fa[u]]) - query(id[u]);
int p = BCC[fa[u]];
if (!p) ans += query(id[fa[fa[u]]]);
else ans += query(id[a[getl(p)]]) + query(id[a[getr(p)]]);
} else {
int bl = getl(BCC[u]), br = getr(BCC[u]);
ans += query(, , tol, ls[a[bl]], rs[a[bl]]) + query(, , tol, ls[a[br]], rs[a[br]]);
if (getl(bl) != br) ans += query(id[a[getl(bl)]]);
if (getr(br) != bl && getr(br) != getl(bl)) ans += query(id[a[getr(br)]]);
}
}
return ans;
}
} seg; int main() {
freopen("in.txt", "r", stdin);
int T;
scanf("%d", &T);
while (T--) {
scanf("%d", &n);
tol = a[] = ;
for (int i = ; i <= n; i++) {
fa[i] = son[i] = BCC[i] = id[i] = vis[i] = ;
vec[i].clear();
}
for (int i = , u, v; i <= n; i++) {
scanf("%d%d", &u, &v);
vec[u].push_back(v);
vec[v].push_back(u);
}
dfs(, );
for (int i = ; i <= a[]; i++)
bfs(a[i]);
seg.build(, , tol);
int q;
scanf("%d", &q);
while (q--) {
int u, k;
char s[];
scanf("%s%d%d", s, &u, &k);
if (s[] == 'M') {
int d;
scanf("%d", &d);
seg.update(u, k, d);
} else {
printf("%lld\n", seg.query(u, k));
}
}
}
return ;
}
终于把这道题给补了...比赛前我居然还在搞这些不考的东西
裸 K 短路，并且是有向无环图，求 $T$ 到其他点的最短路拓扑排序就能解决。
求出 $T$ 到其他所有点的最短路树，记 $d[i]$ 为 $i$ 到 $T$ 的最短路。给每一个点分配一个前趋，如果多个相同则选其中一个。（注意有重边时要记录边而不是记录前趋的点！！！）
走 $S$ 到 $T$ 上的树边即为最短路，走一条非树边 $(u, v, c)$ 则会使费用增大 $d[v] + c - d[u]$。记该花费为非树边的费用，显然树边的费用为 $0$。
将一条从 $S$ 到 $T$ 的路径记为其经过的非树边序列 $p$，那么这条路径的权值和即为 $d[s] + \sum_{(u,v,c) \in p} (d[v] + c - d[u])$
求 $k$ 短路即求第 $k$ 小的合法非树边序列费用之和。
合法的非树边序列为相邻两条非树边 $e$，$f$，$e$ 在 $f$ 之前，$head(f)$ 需为 $tail(e)$ 在 $T$ 上的祖先或相同。
用一个堆来存储搜索的状态，当前的非树边权值和为优先级，再存储最后一条非树边的起点。
往后可以有两个决策，一为直接加上最后一条非树边的终点之后的非树边中，权值最小的那个。
二为将最后一条非树边替换为 $u$ 之后的非树边下一条比这条非树边大的。
发现需要用另一个堆维护每个点往后所有的非树边。发现 $u$ 和 $pre[u]$ 大部分非树边相同，只是多了一些以自身为起点的非树边，那么可以可持久化地添加非树边。
可以用可持久化左偏树，虽然论文里说的是它不可完全可持久化。
还是挺好写的，就是在合并的过程中用新的节点来合并。像线段树合并。
#include <bits/stdc++.h> #define pii pair<int, int>
#define fi first
#define se second const int N = 4e5 + ;
const int INF = 0x3f3f3f3f;
template<class T>inline bool chkmin(T &a, const T &b) { return a > b ? a = b, true : false; }
template<class T>inline bool chkmax(T &a, const T &b) { return a < b ? a = b, true : false; } namespace Heap {
struct Node {
int lp, rp, v, dis, val;
} tree[N * ];
int tol, root[N];
int newnode(int x = , int y = ) {
int p = ++tol;
tree[p].val = x, tree[p].v = y;
tree[p].lp = tree[p].rp = ; tree[p].dis = ;
return p;
}
int merge(int p, int q) {
if (!p || !q) return p + q;
if (tree[p].val < tree[q].val) std::swap(p, q);
int x = newnode();
tree[x] = tree[p];
tree[x].rp = merge(tree[x].rp, q);
if (tree[tree[x].lp].dis < tree[tree[x].rp].dis) std::swap(tree[x].lp, tree[x].rp);
tree[x].dis = tree[tree[x].rp].dis + ;
return x;
}
inline void init() {
tol = ;
tree[].dis = -;
}
} using namespace Heap; int n, k, cnt, id[N][], s, t, deg[N];
int head1[N], head2[N], e, d[N];
struct Ed {
int v, ne, c;
} E[N]; void add(int u, int v, int c) {
E[cnt].v = v; E[cnt].ne = head1[u]; E[cnt].c = c; head1[u] = cnt++;
E[cnt].v = u; E[cnt].ne = head2[v]; E[cnt].c = c; head2[v] = cnt++;
deg[u]++;
} int Q[N], pre[N]; int topo(int S, int *head) {
int l = , r = ;
Q[r++] = S;
d[S] = ;
while (l <= r) {
int u = Q[l++];
for (int i = head[u]; ~i; i = E[i].ne) {
int v = E[i].v;
if (chkmax(d[v], d[u] + E[i].c)) pre[v] = i;
if (!--deg[v]) Q[r++] = v;
}
}
return r;
} int solve() {
scanf("%d%d", &n, &k);
cnt = e = ;
init();
for (int i = ; i <= n; i++)
id[i][] = ++e, id[i][] = ++e;
s = ++e, t = ++e;
for (int i = ; i <= e; i++) {
root[i] = ;
d[i] = -INF;
pre[i] = -;
deg[i] = ;
head1[i] = head2[i] = -;
}
for (int i = ; i < n; i++) {
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
add(id[i][], id[i + ][c], a);
add(id[i][], id[i + ][c], b);
add(id[i][], id[i + ][], );
add(id[i][], id[i + ][], );
}
add(s, id[][], );
add(id[n][], t, );
add(id[n][], t, );
int m = topo(t, head2);
if (k == ) return d[s];
for (int j = ; j < m; j++) {
int u = Q[j];
for (int i = head1[u]; ~i; i = E[i].ne) {
int v = E[i].v;
if (d[v] == INF || (i ^ ) == pre[u]) continue;
root[u] = merge(root[u], newnode(d[v] + E[i].c - d[u], v));
}
if (~pre[u]) root[u] = merge(root[u], root[E[pre[u] ^ ].v]);
}
std::priority_queue<std::pii> que;
que.push(std::pii(d[s] + tree[root[s]].val, root[s]));
for (k -= ; k; k--) {
auto p = que.top(); que.pop();
int i = p.se, j = root[tree[i].v];
if (j) que.push(std::pii(p.fi + tree[j].val, j));
if (tree[i].lp) que.push(std::pii(p.fi - tree[i].val + tree[tree[i].lp].val, tree[i].lp));
if (tree[i].rp) que.push(std::pii(p.fi - tree[i].val + tree[tree[i].rp].val, tree[i].rp));
}
return que.top().fi;
} int main() {
freopen("in.txt", "r", stdin);
int T;
scanf("%d", &T);
while (T--) printf("%d\n", solve());
return ;
}
最新文章
- Springboot框架
- 整数分解 && 质因数分解
- Thinkphp下嵌套UEditor富文本WEB编辑器
- SSAS建模遇到的问题集锦
- 多校3- RGCDQ 分类： 比赛 HDU 2015-07-31 10:50 2人阅读 评论(0) 收藏
- ORA-10456:cannot open standby database;media recovery session may be in process
- foundation框架之反射机制
- 对C#泛型实例化对像--转
- windows cmd命令行下创建文件和文件夹
- GO开发[四]：golang函数
- Jenkins持续集成－自动化部署脚本的实现
- 奥酷HTML5视频直播系统AMS6.0
- java File类常用方法
- Flask框架之 --- 我的第一个个人网站(雏形)
- styled-components解决全局样式'injectGlobal' 废除的问题
- Jedis
- [转]Angular4首页加载慢优化之路
- Codeforces 1101F Trucks and Cities dp (看题解)
- 全排列（Perm）的递归实现算法
- 关于T/G/M/K
热门文章
- k8s之系统组件架构-02
- Linux下Maven私服Nexus3.x环境构建操作记录
- setInterval()调用其他函数时候报错
- go-gin-api 路由中间件 - 日志记录
- springmvc全局异常处理ControllerAdvice区分返回响应类型是页面还是JSON
- 【题解】C2Crni - Crni [COCI2010] [SP7884]
- Qt 的两个许可证区别分析：LGPL 和商业协议
- NIO ByteBuffer的allocate与allocateDirect区别（HeapByteBuffer与DirectByteBuffer的区别）
- thread stack size not set; configure via D:\Program Files\elasticsearch-5.0.0\config\jvm.options or ES_JAVA_OPTS
- ionic 股票列表 网络读取数据，实现下拉刷新，上拉加载