กำหนดน้ำหนักเส้นทาง (Edge Weights) ให้เส้นทางที่ยาวที่สุดน้อยที่สุดใน C++

ที่นี่เราจะดูปัญหาหนึ่ง: กำหนดเส้นทาง (edge) ของต้นไม้หนึ่งเส้นและผลรวม S งานคือกำหนดน้ำหนักให้เส้นทางอื่นๆ ทั้งหมด ทำให้เส้นทางที่ยาวที่สุดในแง่ของน้ำหนัก (weights) เป็นน้อยที่สุด ผลรวมของน้ำหนักที่กำหนดต้องเท่ากับ 'S'

แนวทางง่ายๆ คุณสมบัติของต้นไม้คือเส้นทางหนึ่งสามารถมีโหนดใบ (leaf nodes) ได้สูงสุด 2 โหนด คุณสมบัตินี้จะนำไปสู่คำตอบ ดังนั้นถ้าเรากำหนดน้ำหนักเฉพาะเส้นทางที่เชื่อมโหนดใบ และกำหนดเส้นทางอื่นเป็น 0 เส้นทางที่เชื่อมโหนดใบแต่ละเส้นจะได้รับการกำหนดเป็น:

เนื่องจากเส้นทางสามารถมีโหนดใบได้สูงสุด 2 โหนด ดังนั้นเส้นทางที่ยาวที่สุดจะเป็น:

ตัวอย่างโค้ด

#include <iostream>
#include <vector>
using namespace std;

void insertEdge(int u, int v, vector<int> adj[]) {
    adj[u].push_back(v);
    adj[v].push_back(u);
}

long double pathLength(vector<int> adj[], int sum, int n) {
    int count = 0;
    for (int i = 1; i <= n; i++) {
        if (adj[i].size() == 1)
            count++;
    }
    long double ans = 2.0 * (long double)(sum / (long double)(count));
    return ans;
}

int main() {
    int n = 6;
    vector<int> adj[n + 1];
    insertEdge(1, 2, adj);
    insertEdge(2, 3, adj);
    insertEdge(2, 4, adj);
    insertEdge(4, 5, adj);
    insertEdge(4, 6, adj);
    int sum = 1;
    cout << pathLength(adj, sum, n);
}

ผลลัพธ์

0.5