【CodeForces】【结论】444A DZY Loves Physics

CodeForces 444A DZY Loves Physics

题目大意

给定一张无向图，其中每个点有一个权值$A_u$，每条边有一个权值$B_{u,v}$，要求找出一个子图，使得子图连通且任意两点间存在边则一定要被选中。

求出选出的子图中点权之和除以边权之和的最大值。

分析

结论： 这个子图中仅包含一条边和它的两个端点。

然后就枚举一条边，计算它的答案。然后就完了。。。

证明： 我们只需要证明对于三个连成一条链的点$u,v,w$（$u,w$是端点），选择$u,v,w$取不到最大值即可。

采用反证法：假设选择了$u,v,w$取得了最大值，那么我们可以得到如下不等式：

$$\{\begin{array}{l}\frac{A_u+A_v+A_w}{B_{u,v}+B_{v,w}}\ge \frac{A_u+A_v}{B_{u,v}}\\ \frac{A_u+A_v+A_w}{B_{u,v}+B_{v,w}}\ge \frac{A_w+A_v}{B_{v,w}}\end{array}$$

简单整理一下得到：

$$\{\begin{array}{l}{A}_w\ge \frac{A_v{B}_{u,v}+A_u{B}_{v,w}}{B_{u,v}}\\ A_u\ge \frac{A_w{B}_{u,v}+A_v{B}_{u,v}}{B_{v,w}}\end{array}$$

我们把上面的那个不等式代入下面去得到：

$$\begin{array}{rl}{A}_u& \ge \frac{\frac{A_v{B}_{u,v}+A_u{B}_{v,w}}{B_{u,v}}\times B_{u,v}+A_v{B}_{u,v}}{B_{v,w}}\\ & =\frac{A_v{B}_{u,v}+A_u{B}_{v,w}+A_v{B}_{u,v}}{B_{v,w}}\\ & =A_u+\frac{2A_v{B}_{u,v}}{B_{v,w}}\end{array}$$

移项得到：

$$\frac{2A_v{B}_{u,v}}{B_{v,w}}\le 0$$

由于题目中给定的点权和边权都是正数，所以这个不等式不成立，所以选择一条链不能得到最大值。

故当点权和除以边权和最大时，子图中只有一条边和它的两个端点

参考代码

#include <cstdio>
#include <algorithm>
using namespace std;const int Maxn = 500;int N, M;
int A[Maxn + 5];int main() {
    
#ifdef LOACLfreopen("in.txt", "r", stdin);freopen("out.txt", "w", stdout);
#endifdouble ans = 0;scanf("%d %d", &N, &M);for(int i = 1; i <= N; i++)scanf("%d", &A[i]);for(int i = 1; i <= M; i++) {
    int u, v, w;scanf("%d %d %d", &u, &v, &w);ans = max(ans, 1.0 * (A[u] + A[v]) / w);}printf("%.9f\n", ans);return 0;
}