首页 > 代码库 > Codeforces 444A DZY Loves Physics(图论)
Codeforces 444A DZY Loves Physics(图论)
题目链接:Codeforces 444A DZY Loves Physics
题目大意:给出一张图,图中的每个节点,每条边都有一个权值,现在有从中挑出一张子图,要求子图联通,并且被选中的任意两点,如果存在边,则一定要被选中。问说点的权值和/边的权值和最大是多少。
解题思路:是图论中的一个结论,最多两个节点,所以枚举两条边就可以了。我简单的推了一下,2个点的情况肯定比3个点的优。
假设有3个点a,b,c,权值分别为A,B,C
现a-b,b-c边的权值分别为u,v
那么对于两点的情况有A+Bu,B+Cv
假设有A+Bu≥B+Cv
对于三点来说A+B+Cu+v,有(A+B)?v≥(B+C)?u
比较A+Bu和A+B+Cu+v,两边同乘u?(u+v),得(A+B)?(u+v)和(A+B+C)?u
同减(A+B)?u,(A+B)?v和C?u
因为(A+B)?v≥(B+C)?u≥C?u
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 500;
int n, m;
double val[maxn+5];
int main () {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
scanf("%lf", &val[i]);
double ans = 0, k;
int a, b;
for (int i = 0; i < m; i++) {
scanf("%d%d%lf", &a, &b, &k);
double tmp = (val[a] + val[b]) / k;
if (tmp > ans)
ans = tmp;
}
printf("%.15lf\n", ans);
return 0;
}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。