P10166 题解

Register_int · 2024-02-17 19:02:40 · 题解

显然点两条边不如点一条要优。题目转化为：对于任意两点 u,v 满足 u 能到达 v，求 \min a_u+a_v。

若图原本就有环，那么代价必定为 0。否则说明图 G 是一个有向无环图，可以用拓扑排序维护 dp。设 dp_u 表示所有能到 u 的 v 的 a_v 的最小值，那么答案为 \min_{(u\to v)\in E}dp_u+a_v。

另外还要判凭空造出来一个环的情况，这时也是造二元环最优，代价为 2(a_u+a_v)。处理出最小值与次小值即可。时间复杂度 O(n+m)。

AC 代码

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAXN = 5e5 + 10;

vector<int> g[MAXN]; int d[MAXN];

int n, m, a[MAXN], dp[MAXN]; queue<int> q;

ll x, y, ans;

int main() {
    scanf("%d%d", &n, &m), x = y = 1e9;
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]), dp[i] = a[i];
    for (int i = 1; i <= n; i++) {
        if (a[i] <= x) y = x, x = a[i];
        else if (a[i] < y) y = a[i];
    }
    ans = x + y << 1;
    for (int i = 1, u, v; i <= m; i++) {
        scanf("%d%d", &u, &v), d[v]++;
        g[u].push_back(v);
    }
    for (int i = 1; i <= n; i++) if (!d[i]) q.push(i);
    for (int u; !q.empty(); ) {
        u = q.front(), q.pop();
        for (int v : g[u]) {
            ans = min<ll>(ans, a[v] + dp[u]), dp[v] = min(dp[v], dp[u]);
            if (!--d[v]) q.push(v);
        }
    }
    for (int i = 1; i <= n; i++) if (d[i]) ans = 0;
    printf("%lld", ans);
}