题解：银行转账手续费问题（DFS实现） 问题分析 题目要求在给定的转账网络中，计算从A转账给B时，B收到100元所需的最小金额。每次转账会扣除一定百分比的手续费（z%），实际到账金额为转账金额的(100-z)%。问题转化为寻找一条从A到B的路径，使得该路径上所有转账系数的乘积最大（即手续费损失最小）。最终结果为100除以路径最大乘积。

解题思路 使用深度优先搜索（DFS）遍历所有可能的转账路径：

图建模：用邻接矩阵存储转账关系（mapp[x][y]存储x→y的手续费）

DFS搜索：

从起点A开始搜索，当前转账系数初始为1（100%）

每经过一条边，乘以该边的转账系数(100-z)%

到达终点B时，更新全局最大乘积ans

结果计算：100 / ans（保留8位小数）

代码实现

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

int n, m, a, b;         // 人数、转账对数、起点、终点
int mapp[2005][2005];   // 邻接矩阵存储手续费
int vis[2005];          // 标记访问过的节点
double ans;             // 存储最大转账乘积

void dfs(int start, double now) {
    if (start == b) {   // 到达终点B
        if (now > ans) ans = now;  // 更新最大乘积
        return;
    }
    for (int i = 1; i <= n; i++) {
        // 存在边且未访问过
        if (!vis[i] && mapp[start][i]) {
            vis[i] = 1;  // 标记访问
            // 计算新路径的乘积：(100-手续费)%
            dfs(i, now * (100 - mapp[start][i]) * 0.01);
            vis[i] = 0;  // 回溯
        }
    }
}

int main() {
    cin >> n >> m;
    // 初始化邻接矩阵
    memset(mapp, 0, sizeof(mapp));
    // 读入转账关系
    for (int i = 0; i < m; i++) {
        int x, y, z;
        cin >> x >> y >> z;
        mapp[x][y] = z;
        mapp[y][x] = z;
    }
    cin >> a >> b;
    
    // 初始化访问数组
    memset(vis, 0, sizeof(vis));
    vis[a] = 1;       // 标记起点
    ans = 0;          // 初始化最大乘积
    
    dfs(a, 1.0);      // 从A开始DFS
    
    // 输出结果（保留8位小数）
    printf("%.8f", 100.0 / ans);
    return 0;
}

算法特点 简单直观：DFS直接遍历所有路径，易于理解

回溯机制：通过vis数组标记访问状态，避免重复访问

乘积更新：实时计算路径乘积，到达终点时更新最大值

复杂度分析 时间复杂度：O(n!) 最坏情况下需遍历所有路径

空间复杂度：O(n) 递归栈深度和vis数组空间

局限性 当节点数较大（n>20）时，DFS可能超时。对于本题规模（n≤2000），实际测试中可能无法通过所有测试点。生产环境建议使用Dijkstra算法优化（见优化思路）。

优化思路 对于大规模数据：

使用邻接表：替代邻接矩阵减少空间占用

Dijkstra算法：将转账系数视为"汇率"，求乘积最大路径

剪枝优化：记录到各节点的当前最大乘积，提前终止次优路径

输入示例验证： 输入：3 3 1 2 1 2 3 2 1 3 3 1 3 输出：103.07153164 计算过程：路径1→3乘积最大为0.97，100/0.97≈103.07153164