题目描述

给定一个有N个节点和M条边的无向连通图，每个节点有一个权值。现在要求删除一条边，使得剩下的图分成两个连通分量，且这两个连通分量的权值之和的差值最小。输出这个最小的差值，如果没有合法的删边方案，输出-1。

输入格式
第一行包含两个整数N和M，表示节点的数量和边的数量。

第二行包含N个整数，表示每个节点的权值。

接下来M行，每行包含两个整数u和v，表示一条连接u和v的无向边。

输出格式
输出一个整数，表示最小的权值之和的差值，如果没有合法的删边方案，输出-1。

样例输入
5 5
1 2 3 4 5
1 2
2 3
3 4
4 5
5 1

样例输出
0

解题思路

本题可以使用深度优先搜索（DFS）算法来求解。DFS是一种遍历或搜索图或树数据结构的算法，它从一个起始节点开始，沿着每条分支尽可能深地探索，直到不能再前进为止，然后回溯到上一个节点，继续探索其他分支。DFS通常需要额外的内存，通常是一个栈，来记录已经发现的节点，以便在回溯时能够找到下一个要访问的节点。

对于本题，我们可以枚举所有可能删除的边，并计算删除这条边后剩下的两个连通分量的权值之和。为了方便计算权值之和，我们可以定义一个函数dfs，接受四个参数：一个整数node，表示当前访问的节点；一个布尔向量visited，表示每个节点是否被访问过；一个由整数向量组成的向量adjList，表示图的邻接表；一个整数向量weights，表示每个节点的权值。这个函数返回从node开始深度优先搜索能够到达的所有节点的权值之和。具体地，这个函数做以下操作：

把当前节点标记为已访问；
定义一个变量sum，表示权值之和，初始为当前节点的权值；
遍历当前节点的所有邻居；
如果邻居没有被访问过，则递归地访问邻居，并把返回值加到sum上；
返回sum。
有了这个函数后，我们就可以枚举所有可能删除的边，并计算删除这条边后剩下的两个连通分量的权值之和。具体地，我们做以下操作：

定义一个由整数向量组成的向量adjList，表示图的邻接表；
定义一个布尔向量visited，表示每个节点是否被访问过；
遍历所有边，并把边的两个端点加入到对应的邻接表中；
定义一个变量minDifference，表示最小的权值之差，初始为INT_MAX（最大整数）；
遍历所有边；
把visited向量重新赋值为false；
把边的第一个端点标记为已访问（相当于删除这条边）；
从边的第二个端点开始深度优先搜索，计算第一个连通分量的权值之和，并赋值给sum1；
从节点1开始深度优先搜索，计算第二个连通分量的权值之和，并赋值给sum2（因为题目保证了图是连通的，所以从任意一个未访问的节点开始都可以）；
如果两个连通分量都不为空（即不是删除了桥边），则计算两个连通分量的权值之差的绝对值，并和minDifference比较，取较小值；
如果minDifference没有被更新过，说明没有合法的删边方案，返回-1；否则返回minDifference。
代码实现

以下是ACcode

//F删边问题
#include <bits/stdc++.h> // 引入万能头文件

using i64 = long long; // 定义i64为long long的别名

// 定义一个结构体Edge，表示一条边，包含两个整数u和v，表示边的两个端点
struct Edge {
    i64 u, v;
};

// 定义一个函数dfs，接受四个参数：一个整数node，表示当前访问的节点；一个布尔向量visited，表示每个节点是否被访问过；一个由整数向量组成的向量adjList，表示图的邻接表；一个整数向量weights，表示每个节点的权值。返回从node开始深度优先搜索能够到达的所有节点的权值之和
i64 dfs(i64 node, std::vector<bool> &visited, std::vector<std::vector<i64>> &adjList, std::vector<i64> &weights) {
    visited[node] = true; // 把当前节点标记为已访问
    i64 sum = weights[node]; // 定义一个i64变量sum，表示权值之和，初始为当前节点的权值
    for (i64 neighbor: adjList[node]) { // 遍历当前节点的所有邻居
        if (!visited[neighbor]) { // 如果邻居没有被访问过
            sum += dfs(neighbor, visited, adjList, weights); // 递归地访问邻居，并把返回值加到sum上
        }
    }
    return sum; // 返回sum
}

// 定义一个函数findMinDifference，接受五个参数：两个整数N和M，分别表示节点的数量和边的数量；一个整数向量weights，表示每个节点的权值；一个由Edge结构体组成的向量edges，表示所有边。返回删除一条边后使得剩下的两个连通分量的权值之差最小的值
i64 findMinDifference(i64 N, i64 M, std::vector<i64> &weights, std::vector<Edge> &edges) {
    std::vector<std::vector<i64>> adjList(N + 1); // 定义一个由整数向量组成的向量adjList，表示图的邻接表，大小为N+1（因为节点编号从1开始）
    std::vector<bool> visited(N + 1, false); // 定义一个布尔向量visited，表示每个节点是否被访问过，大小为N+1（因为节点编号从1开始），初始为false
    for (const auto &edge: edges) { // 遍历所有边
        adjList[edge.u].push_back(edge.v); // 把边的两个端点加入到对应的邻接表中
        adjList[edge.v].push_back(edge.u);
    }
    i64 minDifference = INT_MAX; // 定义一个i64变量minDifference，表示最小的权值之差，初始为INT_MAX（最大整数）
    for (const auto &edge: edges) { // 遍历所有边
        visited.assign(N + 1, false); // 把visited向量重新赋值为false
        visited[edge.u] = true; // 把边的第一个端点标记为已访问（相当于删除这条边）
        i64 sum1 = dfs(edge.v, visited, adjList, weights); // 从边的第二个端点开始深度优先搜索，计算第一个连通分量的权值之和，并赋值给sum1
        i64 sum2 = dfs(1, visited, adjList, weights); // 从节点1开始深度优先搜索，计算第二个连通分量的权值之和，并赋值给sum2（因为题目保证了图是连通的，所以从任意一个未访问的节点开始都可以）
        if (sum1 != 0 && sum2 != 0) { // 如果两个连通分量都不为空（即不是删除了桥边）
            minDifference = std::min(minDifference, std::abs(sum1 - sum2)); // 计算两个连通分量的权值之差的绝对值，并和minDifference比较，取较小值
        }
    }
    return (minDifference == INT_MAX) ? -1 : minDifference; // 如果minDifference没有被更新过，说明没有合法的删边方案，返回-1；否则返回minDifference
}

// 主函数
int main() {
    i64 N, M; // 定义两个i64变量N和M，分别表示节点的数量和边的数量
    std::cin >> N >> M; // 输入N和M的值
    std::vector<i64> weights(N + 1); // 定义一个整数向量weights，表示每个节点的权值，大小为N+1（因为节点编号从1开始）
    for (i64 i = 1; i <= N; i++) { // 遍历N个节点
        std::cin >> weights[i]; // 输入每个节点的权值
    }
    std::vector<Edge> edges(M); // 定义一个由Edge结构体组成的向量edges，表示所有边，大小为M
    for (i64 i = 0; i < M; i++) { // 遍历M条边
        std::cin >> edges[i].u >> edges[i].v; // 输入每条边的两个端点
    }
    i64 minDifference = findMinDifference(N, M, weights, edges); // 调用findMinDifference函数，计算最小的权值之差，并赋值给minDifference
    std::cout << minDifference << std::endl; // 输出minDifference
    return 0;
}