JZOJ 6931. 【2020.12.26冬令营模拟】T3
题解
- 考虑每条边的贡献拆开来看，那么式子可以用基本不等式化简求得最大值，但会发现每个点的贡献会算重，可以把每个点的贡献平均分给每条边。
- 但这样子的正确性是无法保证的，不过有20分的特殊数据可以保证其正确性。
- 另外，求最大值可以直接用三分。
- 通过移项可以发现，当答案确定后，每个点拆给与其相连的边的比例系数确定，通过是否能够合理分配和单调性证明后可以直接使用二分解决。
代码
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
using namespace std;
#define N 100010
#define ld long double
#define E 0.000000001
queue<int> q;
ld a[N], b[N * 2], f[N];
int len = 0, last[N], nxt[N * 2], to[N * 2];
int n, ok, fa[N], de[N], d[N], id[N];
void add(int x, int y, ld c) {
to[++len] = y;
nxt[len] = last[x];
last[x] = len;
b[len] = c;
}
void dfs(int k) {
for(int i = last[k]; i; i = nxt[i]) if(to[i] != fa[k]) {
de[k]++, fa[to[i]] = k, id[to[i]] = i, dfs(to[i]);
}
}
void bfs(ld x) {
ok = 1;
for(int i = 1; i <= n; i++) f[i] = x * a[i];
memset(d, 0, sizeof(d));
for(int i = 1; i <= n; i++) if(d[i] == de[i]) q.push(i);
while(!q.empty()) {
int k = q.front();
if(f[k] < 0) ok = 0;
q.pop();
d[fa[k]]++;
f[fa[k]] -= b[id[k]] * b[id[k]] / 4.0 / f[k];
if(d[fa[k]] == de[fa[k]]) q.push(fa[k]);
}
}
int main() {
int i, x, y; ld c;
scanf("%d", &n);
for(i = 1; i <= n; i++) scanf("%Lf", &a[i]);
for(i = 1; i < n; i++) {
scanf("%d%d%Lf", &x, &y, &c);
add(x, y, c), add(y, x, c);
}
dfs(1);
ld l = 0, r = 40000, ans;
while(l <= r) {
ld mid = (l + r) / 2.0;
bfs(mid);
if(!ok) l = mid + E; else r = mid - E, ans = mid;
}
printf("%Lf
", ans);
return 0;
}
自我小结
- 较为熟练地运用数学知识，虽然不是正解，但合理拿到了部分分。
- 与此同时需要注意的是，程序实现数学方法不一定要按部就班，也许会有捷径，如对勾函数的极值可以直接三分。