忘了写题解，但总觉得要写点啥，所以就有了这篇题集。
A – Tree
是个网络流啊，GG。
六中的神仙提出了一种很出色的方法：将树上的边按深度大的往深度小的连，并且流量为\(1\)，费用为\(0\)；对于每一种路径，按深度大的往深度小的连，流量为\(1\)费用为\(c_i\)，并且让源点向深度大的点连边，流量为\(1\)费用为\(0\)，深度小的点向汇点连边，流量为\(1\)费用为\(0\)。
我们可以求出最小费用最大流，然后这最小费用就相当于最小割，我们可以对路径贡献求和再减去费用得到答案。
// A.cpp
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 2e5 + 200;
typedef long long ll;
const ll INF = 0x3f3f3f3f3f3f3f3f;
int n, m, head[MAX_N], current, dep[MAX_N], T, START, END, deg[MAX_N];
int pre[MAX_N], flow[MAX_N];
ll dist[MAX_N];
bool vis[MAX_N];
struct edge
{
int to, nxt, weight, cost;
} edges[MAX_N << 2];
struct path
{
int u, v, d;
} paths[MAX_N];
vector<edge> G[MAX_N];
void fileIO()
{
freopen("tree.in", "r", stdin);
freopen("tree.out", "w", stdout);
}
inline char nc()
{
static char buf[1000000], *p1 = buf, *p2 = buf;
return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1000000, stdin), p1 == p2) ? EOF : *p1++;
}
int read()
{
int x = 0, f = 1;
char ch = nc();
while (!isdigit(ch))
{
if (ch == '-')
f = -1;
ch = nc();
}
while (isdigit(ch))
x = (x << 3) + (x << 1) + ch - '0', ch = nc();
return x * f;
}
void addpath(int src, int dst, int weight, int cost)
{
edges[current].to = dst, edges[current].nxt = head[src];
edges[current].weight = weight, edges[current].cost = cost;
head[src] = current++;
}
void addtube(int src, int dst, int weight, int cost)
{
addpath(src, dst, weight, cost);
addpath(dst, src, 0, -cost);
}
bool spfa_min(int src)
{
memset(dist, 0x3f, sizeof(dist));
memset(vis, false, sizeof(vis));
memset(flow, 0, sizeof(flow));
queue<int> q;
q.push(src), vis[src] = true, dist[src] = 0;
flow[src] = 0x3f3f3f3f;
while (!q.empty())
{
int u = q.front();
q.pop();
vis[u] = false;
for (int i = head[u]; i != -1; i = edges[i].nxt)
if (dist[edges[i].to] > dist[u] + edges[i].cost && edges[i].weight > 0)
{
dist[edges[i].to] = dist[u] + edges[i].cost;
flow[edges[i].to] = min(edges[i].weight, flow[u]);
pre[edges[i].to] = i;
if (!vis[edges[i].to])
q.push(edges[i].to), vis[edges[i].to] = true;
}
}
return flow[END] != 0;
}
ll mcmf()
{
ll ans = 0;
while (spfa_min(START))
{
ans += dist[END] * flow[END];
int pt = END, i = pre[pt];
while (pt != START)
{
edges[i].weight -= flow[END], edges[i ^ 1].weight += flow[END];
pt = edges[i ^ 1].to, i = pre[pt];
}
}
return ans;
}
void dfs(int u, int fa)
{
dep[u] = dep[fa] + 1;
for (int i = 0, siz_ = G[u].size(); i < siz_; i++)
if (G[u][i].to != fa)
dfs(G[u][i].to, u), addtube(G[u][i].to, u, G[u][i].weight, 0);
}
void initialize()
{
memset(head, -1, sizeof(head)), current = 0;
for (int i = 1; i <= n; i++)
G[i].clear();
START = 0, END = n + 1, memset(deg, 0, sizeof(deg));
}
int main()
{
T = read();
while (T--)
{
n = read(), m = read();
initialize();
for (int i = 1, u, v, w; i <= n - 1; i++)
{
u = read(), v = read(), w = read();
G[u].push_back(edge{v, 0, w, 0}), G[v].push_back(edge{u, 0, w, 0});
}
dfs(1, 0);
ll answer = 0;
for (int i = 1, u, v, w; i <= m; i++)
{
u = read(), v = read(), w = read();
if (dep[u] < dep[v])
swap(u, v);
answer += w, addtube(u, v, 1, w);
addtube(START, u, 1, 0), addtube(v, END, 1, 0);
}
printf("%lld\n", answer - mcmf());
}
return 0;
}
B – Dice
这题还蛮有趣的，期望部分比较板但方差的部分还真的挺难的。
先考虑期望的30分，我们设置\(f[i][j]\)为前\(i\)次中最后一次选\(j \in [1, 6]\)的概率，设置\(g[i][j]\)为相应的期望。那么，转移的时候需要注意概率并不是直接乘上\(p_j\)，而是需要考虑重复投掷的情况：
\[ \sum_{t = 0}^{\infty} p_j p_k^t = \frac{p_j}{1 – p_k} \]
这其实是个几何级数，把\(p_j\)提出来之后套公式即可。我们得到了转移时的概率。那么，期望也就很好求了：
\[ g[i][j] = \sum_{k = 1}^6 [k \neq j] g[i – 1][k] \frac{p_j}{1 – p_k} + j \cdot f[i][j] \]
30 分到手。那么，我们来看方差的部分，列式展开：
\[ (ans – E[ans])^2 = ans^2 – 2ansE[ans] + E[ans]^2 \]
由于\(E[ans] = p_{ans} \cdot ans\)，那么自然的，\(ansE[ans] = p_ans \cdot ans^2 = E[ans]^2\)，就剩下了：
\[ ans^2 – E[ans]^2 \]
第二个部分直接平方即可；第一个部分比较麻烦，因为涉及到平方的期望。我们仍可以设置\(s[i][j]\)，那么转移则是：
\[ s[i][j] = \sum_{k = 1}^6 [j \neq k] s[i – 1][k] \frac{p_j}{1 – p_k} + j^2 f[i][j] + 2j(g[i][j] – f[i][j]\cdot j) \]
其中比较特别的是\((g[i][j] – f[i][j] \cdot j)\)，回顾上面的式子，发现这个其实就是上一轮转移到当前状态的所有线性级别的期望（有点绕，也就是说都一次项）。
卡精度就把\(ans\)换成\(\frac{ans}{n}\)，然后就可以过了。（有点玄学）
// B.cpp
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 1e5 + 200;
typedef long double ld;
int n;
ld pi[10], f[MAX_N][7], g[MAX_N][7], s[MAX_N][7];
void fileIO()
{
freopen("dice.in", "r", stdin);
freopen("dice.out", "w", stdout);
}
int main()
{
// fileIO();
for (int i = 1; i <= 6; i++)
cin >> pi[i], f[1][i] = pi[i];
scanf("%d", &n);
for (int i = 2; i <= n; i++)
for (int j = 1; j <= 6; j++)
for (int k = 1; k <= 6; k++)
if (j != k)
f[i][j] += f[i - 1][k] * ld(pi[j] / (1.0 - pi[k]));
for (int i = 1; i <= n; i++)
for (int j = 1; j <= 6; j++)
{
for (int k = 1; k <= 6; k++)
if (j != k)
g[i][j] += g[i - 1][k] * ld(pi[j] / (1.0 - pi[k]));
g[i][j] += f[i][j] * j;
}
ld ans1 = 0, ans2 = 0;
for (int i = 1; i <= 6; i++)
ans1 += g[n][i];
ld tmp = ans1 / n;
for (int i = 1; i <= 6; i++)
f[1][i] = pi[i] * (i - tmp), g[1][i] = pi[i], s[1][i] = (i - tmp) * (i - tmp) * pi[i];
for (int i = 2; i <= n; i++)
for (int j = 1; j <= 6; j++)
{
f[i][j] = g[i][j] = 0;
ld tmp_sum = 0;
for (int k = 1; k <= 6; k++)
if (j != k)
{
f[i][j] += f[i - 1][k] * pi[j] / (1.0 - pi[k]), tmp_sum += 1.0 * pi[j] * g[i - 1][k] / (1 - pi[k]);
s[i][j] += s[i - 1][k] * ld(pi[j] / (1.0 - pi[k]));
}
s[i][j] += 2.0 * (j - tmp) * f[i][j] + tmp_sum * (j - tmp) * (j - tmp), f[i][j] += tmp_sum * (j - tmp);
g[i][j] = tmp_sum;
}
for (int i = 1; i <= 6; i++)
ans2 += s[n][i];
printf("%.10Lf\n%.10Lf\n", ans1, ans2);
return 0;
}