In competitive programming and system design, efficiently navigating complex networks and optimizing resource allocation often require mastery of graph algorithms. The following collection demonstrates implementations for several classic challenges, including broadcast optimization, structural analysis of trees, and constrained dynamic programming.

Optimizing Broadcast Initiation Nodes

When managing a communication network, identifying a central relay point that minimizes the maximum propagation delay to all other nodes is critical. This can be approached by calculating the shortest path from every candidate source and selecting the one with the lowest peak latency. The algorithm below iterates through each node, performing a traversal to determine reachabiilty and maximum travel time.

#include <iostream>
#include <vector>
#include <queue>
#include <limits>

using namespace std;

struct Connection {
    int destination;
    int duration;
};

int identifyOptimalSource(int n, vector<vector<Connection>>& network) {
    vector<long long> minimalLatency(n + 1, numeric_limits<long long>::max());
    vector<bool> isReachable(n + 1, false);
    int bestCandidate = -1;
    long long globalMinMaxTime = numeric_limits<long long>::max();

    for (int startNode = 1; startNode <= n; ++startNode) {
        priority_queue<pair<long long, int>, vector<pair<long long, int> >, greater<pair<long long, int> >> pq;
        fill(isReachable.begin(), isReachable.end(), false);
        
        isReachable[startNode] = true;
        minimalLatency[startNode] = 0;
        pq.push({0, startNode});

        while (!pq.empty()) {
            auto [currentDist, currentU] = pq.top();
            pq.pop();

            if (currentDist > minimalLatency[currentU]) continue;

            for (auto& link : network[currentU]) {
                int nextV = link.destination;
                int weight = link.duration;

                if (!isReachable[nextV] || minimalLatency[currentU] + weight < minimalLatency[nextV]) {
                    isReachable[nextV] = true;
                    minimalLatency[nextV] = minimalLatency[currentU] + weight;
                    pq.push({minimalLatency[nextV], nextV});
                }
            }
        }

        bool fullyConnected = true;
        long long maxForThisSource = 0;
        for (int i = 1; i <= n; ++i) {
            if (!isReachable[i]) {
                fullyConnected = false;
                break;
            }
            maxForThisSource = max(maxForThisSource, minimalLatency[i]);
        }

        if (fullyConnected) {
            if (globalMinMaxTime > maxForThisSource) {
                globalMinMaxTime = maxForThisSource;
                bestCandidate = startNode;
            } else if (globalMinMaxTime == maxForThisSource) {
                if (bestCandidate == -1 || startNode < bestCandidate) {
                    bestCandidate = startNode;
                }
            }
        }
    }

    return bestCandidate;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    while (cin >> n && n != 0) {
        vector<vector<Connection>> network(n + 1);
        for (int i = 1; i <= n; ++i) {
            int m;
            cin >> m;
            for (int j = 0; j < m; ++j) {
                int dest, t;
                cin >> dest >> t;
                network[i].push_back({dest, t});
            }
        }
        
        cout << identifyOptimalSource(n, network) << "\n";
    }
    return 0;
}

Determining the Longest Path in a Tree

The diameter of a tree repreesnts the longest path between any two leaves. An efficient strategy involves running a Depth First Search (DFS) twice. First, traverse from an arbitrary node to find the farthest node. Second, initiate another traversal from this farthest node; the maximum distance reached defines the diameter.

#include <algorithm>
#include <vector>
#include <iostream>

using namespace std;

const int MAX_NODES = 100005;
vector<int> adjacency[MAX_NODES];
bool visited[MAX_NODES];
int depth[MAX_NODES];

void findFarthest(int u, int p, int &farestNode, int &maxDistance) {
    visited[u] = true;
    if (depth[u] > maxDistance) {
        maxDistance = depth[u];
        farestNode = u;
    }
    for (int v : adjacency[u]) {
        if (v != p && !visited[v]) {
            depth[v] = depth[u] + 1;
            findFarthest(v, u, farestNode, maxDistance);
        }
    }
}

int calculateTreeDiameter(int n) {
    fill(visited, visited + n + 1, false);
    fill(depth, depth + n + 1, 0);
    
    int candidateA = 0, maxDistA = 0;
    findFarthest(1, -1, candidateA, maxDistA);

    fill(visited, visited + n + 1, false);
    fill(depth, depth + n + 1, 0);
    
    int maxDistB = 0;
    findFarthest(candidateA, -1, candidateA, maxDistB);
    
    return maxDistB;
}

int main() {
    int n;
    if (cin >> n && n) {
        for (int i = 0; i < n - 1; ++i) {
            int u, v;
            cin >> u >> v;
            adjacency[u].push_back(v);
            adjacency[v].push_back(u);
        }
        cout << calculateTreeDiameter(n) << endl;
    }
    return 0;
}

Aggregating Round-Trip Distances

In scenarios requiring bidirectional data transmission, calculating the sum of shortest paths from a source to all destinations and back is useful. By utilizing Dijkstra's algorithm on both the original graph and its transpose, we can derive the aggregate travel costs efficiently.

#include <queue>
#include <vector>
#include <limits>

using namespace std;
typedef long long ll;
typedef pair<ll, int> pll;

const ll INF = numeric_limits<ll>::max();

vector<ll> runDijkstra(ll start, ll n, vector<vector<pll>>& adj) {
    vector<ll> d(n + 1, INF);
    priority_queue<pll, vector<pll>, greater<pll>> pq;
    
    d[start] = 0;
    pq.push({0, start});

    while(!pq.empty()){
        ll dist = pq.top().first;
        int u = pq.top().second;
        pq.pop();

        if (dist > d[u]) continue;

        for(auto &edge : adj[u]){
            int v = edge.second;
            ll w = edge.first;
            if(d[u] + w < d[v]){
                d[v] = d[u] + w;
                pq.push({d[v], v});
            }
        }
    }
    return d;
}

int solveAggregateCost(ll N, ll M, ll K) {
    // Read inputs and build graph logic here based on problem specifics
    // Example placeholder for edge construction:
    // ...
    return 0; 
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    ll n;
    if (cin >> n) {
        // Placeholder execution for demonstration
        cout << 0 << endl;
    }
    return 0;
}

Maximum Bipartite Matching via Augmenting Paths

Finding the largest set of edges without shared vertices in a bipartite graph is solved using the Hungarian algorithm concept via recursive DFS. The process attempts to match every node in the left partition, backtracking if a conflict arises to free up a vertex.

#include <iostream>
#include <cstring>
#include <vector>

using namespace std;

const int N = 7005;
vector<int> adj[N];
int matchVal[N];
bool visArr[N];

bool dfsMatch(int u) {
    for (int v : adj[u]) {
        if (visArr[v]) continue;
        visArr[v] = true;
        if (matchVal[v] == -1 || dfsMatch(matchVal[v])) {
            matchVal[v] = u;
            return true;
        }
    }
    return false;
}

int main() {
    int n;
    while (cin >> n && n) {
        memset(matchVal, -1, sizeof(matchVal));
        vector<int> degree(n + 1);
        
        for (int i = 1; i <= n; ++i) {
            int k;
            cin >> k;
            for (int j = 0; j < k; ++j) {
                int neighbor;
                cin >> neighbor;
                adj[i].push_back(neighbor);
                adj[neighbor].push_back(i);
            }
        }

        int matchingCount = 0;
        for (int i = 1; i <= n; ++i) {
            memset(visArr, false, sizeof(visArr));
            if (dfsMatch(i)) matchingCount++;
        }
        cout << (matchingCount / 2) << endl;
        
        // Reset adjacency for next case
        for(int i=1; i<=n; ++i) adj[i].clear();
    }
    return 0;
}

Shortest Path in Layered Graph Structures

Some problems involve transitions across states over time or layers. By duplicating the graph nodes for each layer ($u \times k + t$), we can model these constraints as standard shortest path problems using a modified Dijkstra approach.

#include <cstdio>
#include <queue>
#include <algorithm>

using namespace std;

const int MAXN = 110005;
const int INF = 0x3f3f3f3f;

struct Edge {
    int to, next, weight;
} edges[MAXN * 5];
int head[MAXN * 5], cntEdges;

void insertEdge(int u, int v, int w) {
    edges[++cntEdges] = {v, head[u], w};
    head[u] = cntEdges;
}

int distVal[MAXN];
bool visitedNode[MAXN];

void computeShortestPath(int source, int totalNodes) {
    priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> >> pq;
    fill(distVal, distVal + totalNodes + 1, INF);
    
    distVal[source] = 0;
    pq.push({0, source});

    while (!pq.empty()) {
        int d = pq.top().first;
        int u = pq.top().second;
        pq.pop();

        if (visitedNode[u]) continue;
        visitedNode[u] = true;

        for (int e = head[u]; e; e = edges[e].next) {
            int v = edges[e].to;
            if (distVal[u] + edges[e].weight < distVal[v]) {
                distVal[v] = distVal[u] + edges[e].weight;
                pq.push({distVal[v], v});
            }
        }
    }
}

int main() {
    int n, m, k, s, t;
    scanf("%d%d%d%d%d", &n, &m, &k, &s, &t);
    
    // Build layered graph structure
    // ... Implementation details omitted for brevity
    
    printf("%d\n", distVal[t + k * n]);
    return 0;
}

Constrained Edge Selection Using Tree DP

To maximize weight accumulation by selecting a limited number of edges within a tree hierarchy, a bottom-up dynamic programming approach is effective. We define dp\[u\]\[j\] as the maximum value obtainable in the subtree rooted at u using exactly j selected edges.

#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

const int MAX_N = 105;
struct NodeInfo {
    int weight, destination, nextIndex;
} edgeData[MAX_N * 2];

int headList[MAX_N], edgeCount;
int dpTable[MAX_N][MAX_N];
int subtreeSize[MAX_N];

void addLink(int u, int v, int w) {
    edgeCount++;
    edgeData[edgeCount] = {w, v, headList[u]};
    headList[u] = edgeCount;
}

void executeDP(int u, int parent, int limit) {
    subtreeSize[u] = 0;
    dpTable[u][0] = 0;

    for (int e = headList[u]; e; e = edgeData[e].nextIndex) {
        int v = edgeData[e].destination;
        if (v == parent) continue;
        
        executeDP(v, u, limit);
        subtreeSize[u]++;

        for (int j = min(subtreeSize[u], limit); j >= 0; j--) {
            for (int k = 0; k < j && k < subtreeSize[v]; k++) {
                dpTable[u][j] = max(dpTable[u][j], dpTable[u][j - k - 1] + dpTable[v][k] + edgeData[e].weight);
            }
        }
    }
}

int main() {
    int n, m;
    if (scanf("%d%d", &n, &m) != EOF) {
        edgeCount = 0;
        memset(headList, 0, sizeof(headList));
        for (int i = 1; i < n; i++) {
            int u, v, w;
            scanf("%d%d%d", &u, &v, &w);
            addLink(u, v, w);
            addLink(v, u, w);
        }

        executeDP(1, 0, m);
        printf("%d\n", dpTable[1][m]);
    }
    return 0;
}