PHP实现：最大化边端点值的和-php教程-PHP中文网

PHP实现：最大化边端点值的和

花韻仙語

发布： 2025-10-18 10:52:01

原创

609人浏览过

php实现：最大化边端点值的和

本文档详细介绍了如何使用PHP解决最大化图的边端点值的和的问题。通过构建顶点计数数组，并根据顶点出现频率分配权重，最终计算出最大可能的和。文章提供了经过测试的PHP代码示例，并解释了其实现逻辑和注意事项，帮助读者理解和应用该算法。

问题描述

给定一个包含 N 个顶点的图，以及描述边的两个数组 A 和 B，其中 A[i] 和 B[i] 表示第 i 条边的两个端点。目标是为每个顶点分配一个权重，权重范围从 1 到 N，使得所有边的端点权重之和最大。

解决方案

核心思想是为出现频率最高的顶点分配最大的权重 N，为出现频率第二高的顶点分配权重 N-1，以此类推。

算法步骤：

立即学习“PHP免费学习笔记（深入）”；

统计顶点出现次数： 创建一个关联数组 $vertextCount，用于记录每个顶点在数组 A 和 B 中出现的次数。
分配权重： 创建一个关联数组 $wightArr，用于存储每个顶点的权重。根据 $vertextCount 中顶点出现的次数，按照降序分配权重，出现次数最多的顶点分配权重 N，以此类推。
计算总和： 遍历数组 A 和 B，计算每条边的端点权重之和，并将所有边的权重和累加得到最终结果。

PHP 代码示例：

造点AI

夸克 · 造点AI

325

查看详情

<?php

function solution(int $N, array $A, array $B): int
{
    if (count($A) != count($B) || !is_int($N)) {
        return 0; // 或者抛出异常，根据实际需求处理
    }

    $vertextCount = [];
    foreach ($A as $val) {
        if (!isset($vertextCount[$val])) {
            $vertextCount[$val] = 0;
        }
        $vertextCount[$val] += 1;
    }

    foreach ($B as $val) {
        if (!isset($vertextCount[$val])) {
            $vertextCount[$val] = 0;
        }
        $vertextCount[$val] += 1;
    }

    if (count($vertextCount) < $N) {
        $vertextCount[$N] = 0; // 确保所有顶点都在考虑范围内
    }

    $VC = $vertextCount;
    $tn = $N;
    $wightArr = [];
    while (count($VC) > 0) {
        $maxKey = array_search(max($VC), $VC, true); // 找到最大值的键名
        $wightArr[$maxKey] = $tn;
        unset($VC[$maxKey]);
        $tn--;
    }

    $sum = 0;
    foreach ($A as $k => $val) {
        $sum += $wightArr[$A[$k]] + $wightArr[$B[$k]];
    }
    return $sum;
}

// 示例用法
$A = [2, 2, 1, 2];
$B = [1, 3, 4, 4];
$N = 5;

echo $sum = solution($N, $A, $B); // 输出结果
?>

登录后复制

代码解释：