思路: DFS

题目保证路在无向图上一定是个环，我们要做的就是使得这个图是顺时针的有向图还是逆时针的有向图。

考虑顺时针和逆时针两种情况即可。

时间复杂度：$O(n)$

代码

C++

#include <bits/stdc++.h>
using namespace std;

const int INF = 0x3f3f3f3f;

void dfs(vector<vector<pair<int, int>>>& edges, int u, int fa, int& ans, int res) {
    if (u == 0) {
        ans = min(ans, res);
        return;
    }

    for (auto& edge : edges[u]) {
        int v = edge.first;
        int w = edge.second;

        if (v == fa)
            continue;

        dfs(edges, v, u, ans, res + w);
    }
}

int main() {
    int n;
    cin >> n;

    vector<vector<pair<int, int>>> edges(n);
    for (int i = 0; i < n; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        u -= 1;
        v -= 1;

        edges[u].push_back({v, 0});
        edges[v].push_back({u, w});
    }

    int ans = (n > 2) ? INF : 0;
    dfs(edges, edges[0][0].first, 0, ans, edges[0][0].second);
    dfs(edges, edges[0][1].first, 0, ans, edges[0][1].second);

    cout << ans << "\n";

    return 0;
}

Python

# dfs 过深超时，需要手写递归栈

n = int(input())

edges = [[] for i in range(n)]
for i in range(n):
    u, v, w = map(int, input().split())
    u -= 1
    v -= 1

    # 本来就存在一条 u 到 v 的边，无需修改
    edges[u].append([v, 0])
    # 修改 u 到 v 的边反向，需要 w
    edges[v].append([u, w])

# 对于每个点来说，一条入边，一条出边
# 枚举 0 号点为起点，其中一条边为入边，另一条边为出边

ans = 0x3f3f3f3f if n > 2 else 0


def dfs(u, fa, res):
    global ans
    if u == 0:
        ans = min(ans, res)
        return

    for v, w in edges[u]:
        if v == fa:
            continue
        dfs(v, u, res + w)
    return


dfs(edges[0][0][0], 0, edges[0][0][1])
dfs(edges[0][1][0], 0, edges[0][1][1])

print(ans)

n = int(input())

edges = [[] for i in range(n)]
for i in range(n):
    u, v, w = map(int, input().split())
    u -= 1
    v -= 1

    # 本来就存在一条 u 到 v 的边，无需修改
    edges[u].append([v, 0])
    # 修改 u 到 v 的边反向，需要 w
    edges[v].append([u, w])

# 对于每个点来说，一条入边，一条出边
# 枚举 0 号点为起点，其中一条边为入边，另一条边为出边

# 由于python dfs 会爆栈，这里手动模拟栈
def mydfs(edge_number):
    if edge_number == 1:
        x = 1
    res = edges[0][edge_number][1]
    stk = [0, edges[0][edge_number][0]]
    while stk[-1] != 0:
        for i in range(len(edges[stk[-1]])):
            v, w = edges[stk[-1]][i]
            if v == stk[-2]:
                continue
            res += w
            stk.append(v)
            break
    return res


print(min(mydfs(0), mydfs(1)))

Java

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {

    static final int INF = 0x3f3f3f3f;

    static void dfs(List<List<Pair<Integer, Integer>>> edges, int u, int fa, int[] ans, int res) {
        if (u == 0) {
            ans[0] = Math.min(ans[0], res);
            return;
        }

        for (Pair<Integer, Integer> edge : edges.get(u)) {
            int v = edge.first;
            int w = edge.second;

            if (v == fa)
                continue;

            dfs(edges, v, u, ans, res + w);
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();

        List<List<Pair<Integer, Integer>>> edges = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            edges.add(new ArrayList<>());
        }

        for (int i = 0; i < n; i++) {
            int u = scanner.nextInt() - 1;
            int v = scanner.nextInt() - 1;
            int w = scanner.nextInt();

            edges.get(u).add(new Pair<>(v, 0));
            edges.get(v).add(new Pair<>(u, w));
        }

        int[] ans = { (n > 2) ? INF : 0 };
        dfs(edges, edges.get(0).get(0).first, 0, ans, edges.get(0).get(0).second);
        dfs(edges, edges.get(0).get(1).first, 0, ans, edges.get(0).get(1).second);

        System.out.println(ans[0]);
    }

    static class Pair<U, V> {
        U first;
        V second;

        Pair(U first, V second) {
            this.first = first;
            this.second = second;
        }
    }
}

题目描述

现在有一个城市，城市中有 $n$ 个景点，$n$ 条路，这 $n$ 条路构成了一个环形路，但是每条路都是单向路。

作为这个城市中最有名的工程师，小红被邀请来修路。市长希望修完后的路，可以从任意一个景点 $A$ 到达任意一个景点 $B$ 。

但是，由于城市资金有限，修完后的路依旧只能是单向路，对于第 $i$ 条路，直接连接了景点 $u_i$ 和景点 $v_i$ ，但是需要花费 $w_i$ 的资金。

为了锻炼你的能力，小红想问问你在这种情况下，最少花费多少资金可以使得修完后的路，可以从任意一个景点 $A$ 到达任意一个景点 $B$ 。

输入描述

第一行，一个整数 $n(2\leq n\leq 10^5)$，表示景点个数

接下来 $n$ 行，每行三个整数 $u_i,v_i,w_i$， 表示一条从 $u_i$ 到 $v_i(1\leq u_i,v_i\leq n)$ 的有向道路，修改这条路的方向需要花费 $w_i(1\leq w_i\leq 10^4)$ 的资金，保证每个景点都恰好有两条路。

输出描述

一个整数，表示使得修完后的路，可以从任意一个景点 $A$ 到达任意一个景点 $B$ 的最少资金。

样例

输入

3
1 2 1
3 2 10
3 1 2

输出

3

说明

改变第一条路的方向和第三条路的方向，需要资金为 $3$ 。