PHP 实现边端点值最大和算法详解-php教程-PHP中文网

PHP 实现边端点值最大和算法详解

心靈之曲

发布： 2025-10-18 10:06:13

原创

795人浏览过

php 实现边端点值最大和算法详解

本文旨在提供一种使用 PHP 语言解决“计算图中边端点可能的最大和”问题的详细教程。该问题涉及图的顶点和边，目标是为每个顶点分配权重，使得所有边的端点权重之和最大化。本文将深入解析算法思路，并提供可执行的 PHP 代码示例，同时也会讨论一些注意事项。

问题描述

给定一个图，由 N 个顶点和一些边组成。每条边连接两个顶点 A[i] 和 B[i]。目标是为每个顶点分配一个权重，权重范围是 1 到 N，每个权重只能使用一次。目的是最大化所有边的端点权重之和。

算法思路

核心思想是贪心算法。要使总和最大化，应该将最大的权重分配给出现次数最多的顶点。

统计顶点出现次数： 遍历所有边，统计每个顶点在所有边中出现的次数。
权重分配： 将顶点按照出现次数降序排列。然后，从最大的权重 N 开始，依次分配给出现次数最多的顶点。
计算总和： 遍历所有边，计算每条边的端点权重之和，并将所有边的权重和加起来。

PHP 代码实现

<?php

function solution(int $N, array $A, array $B): int
{
    if (count($A) != count($B) || !is_int($N)) {
        return false; // 输入验证
    }

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

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

    if (count($vertexCount) < $N) {
        for ($i = 1; $i <= $N; $i++){
            if(!isset($vertexCount[$i])){
                $vertexCount[$i] = 0;
            }
        }

    }

    arsort($vertexCount); // 按照出现次数降序排列

    $weightArr = [];
    $tn = $N;
    foreach ($vertexCount as $vertex => $count) {
        $weightArr[$vertex] = $tn;
        $tn--;
    }

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

    return $sum;
}

// 示例
$N = 5;
$A = [2, 2, 1, 2];
$B = [1, 3, 4, 4];
$result = solution($N, $A, $B);
echo "Maximum sum: " . $result . PHP_EOL; // 输出：Maximum sum: 26

$N = 4;
$A = [1, 2, 3, 4];
$B = [2, 3, 4, 1];

$result = solution($N, $A, $B);
echo "Maximum sum: " . $result . PHP_EOL; // 输出：Maximum sum: 20
?>

登录后复制

代码解释：