A21324.网络吞吐量 全站第一题解

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

const long long INF = std::numeric_limits<long long>::max();
const int MAXN = 505;
const int MAX_FLOW_NODES = 2 * MAXN;

int n, m;
std::vector<std::pair<int, int>> adj[MAXN];
long long dist_from_1[MAXN];
long long dist_from_n[MAXN];

struct Edge {
    int to;
    long long capacity;
    int rev;
};

std::vector<Edge> flow_graph[MAX_FLOW_NODES];
int level[MAX_FLOW_NODES];
int iter[MAX_FLOW_NODES];

void dijkstra(int start_node, long long dist[]) {
    for (int i = 1; i <= n; ++i) {
        dist[i] = INF;
    }
    dist[start_node] = 0;
    std::priority_queue<std::pair<long long, int>, std::vector<std::pair<long long, int>>, std::greater<std::pair<long long, int>>> pq;
    pq.push({0, start_node});

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

        if (current_d > dist[u]) {
            continue;
        }

        for (auto& edge : adj[u]) {
            int v = edge.first;
            int weight = edge.second;
            if (dist[u] != INF && dist[u] + weight < dist[v]) {
                dist[v] = dist[u] + weight;
                pq.push({dist[v], v});
            }
        }
    }
}

void add_edge(int from, int to, long long capacity) {
    flow_graph[from].push_back({to, capacity, static_cast<int>(flow_graph[to].size())});
    flow_graph[to].push_back({from, 0, static_cast<int>(flow_graph[from].size() - 1)});
}

bool bfs_dinic(int s, int t) {
    std::fill(level, level + 2 * n + 2, -1);
    std::queue<int> q;
    level[s] = 0;
    q.push(s);
    while (!q.empty()) {
        int v = q.front();
        q.pop();
        for (const auto& edge : flow_graph[v]) {
            if (edge.capacity > 0 && level[edge.to] < 0) {
                level[edge.to] = level[v] + 1;
                q.push(edge.to);
            }
        }
    }
    return level[t] != -1;
}

long long dfs_dinic(int v, int t, long long f) {
    if (v == t) {
        return f;
    }
    for (int& i = iter[v]; i < flow_graph[v].size(); ++i) {
        Edge& e = flow_graph[v][i];
        if (e.capacity > 0 && level[v] < level[e.to]) {
            long long d = dfs_dinic(e.to, t, std::min(f, e.capacity));
            if (d > 0) {
                e.capacity -= d;
                flow_graph[e.to][e.rev].capacity += d;
                return d;
            }
        }
    }
    return 0;
}

long long max_flow(int s, int t) {
    long long flow = 0;
    while (bfs_dinic(s, t)) {
        std::fill(iter, iter + 2 * n + 2, 0);
        long long f;
        while ((f = dfs_dinic(s, t, INF)) > 0) {
            flow += f;
        }
    }
    return flow;
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    std::cin >> n >> m;

    std::vector<std::tuple<int, int, int>> edges;
    for (int i = 0; i < m; ++i) {
        int u, v, w;
        std::cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
        edges.emplace_back(u, v, w);
    }

    std::vector<long long> capacities(n + 1);
    for (int i = 1; i <= n; ++i) {
        std::cin >> capacities[i];
    }

    dijkstra(1, dist_from_1);
    dijkstra(n, dist_from_n);

    long long shortest_path_dist = dist_from_1[n];

    for (int i = 1; i <= n; ++i) {
        long long cap = capacities[i];
        if (i == 1 || i == n) {
            cap = INF;
        }
        add_edge(i, i + n, cap);
    }

    for (const auto& edge : edges) {
        int u, v, w;
        std::tie(u, v, w) = edge;
        if (dist_from_1[u] != INF && dist_from_n[v] != INF && dist_from_1[u] + w + dist_from_n[v] == shortest_path_dist) {
            add_edge(u + n, v, INF);
        }
        if (dist_from_1[v] != INF && dist_from_n[u] != INF && dist_from_1[v] + w + dist_from_n[u] == shortest_path_dist) {
            add_edge(v + n, u, INF);
        }
    }
    
    int source_node = 1 + n;
    int sink_node = n;
    
    long long result = max_flow(source_node, sink_node);
    std::cout << result << '\n';

    return 0;
}