CF1082G Petya and Graph

Petya 有一个简单图（即没有自环和重边的图），该图包含 $n$ 个顶点和 $m$ 条边。 第 $i$ 个顶点的权值为 $a_i$。 第 $i$ 条边的权值为 $w_i$。 一个子图是指图中某些顶点的集合以及某些边的集合。边的集合必须满足：集合中的每一条边的两个端点都属于所选的顶点集合。 子图的权值定义为其所有边的权值之和减去其所有顶点的权值之和。你需要求出给定图的子图的最大权值。保证图中没有自环和重边。

第一行包含两个整数 $n$ 和 $m$（$1 \le n \le 10^3, 0 \le m \le 10^3$），分别表示图中的顶点数和边数。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^9$），表示每个顶点的权值。 接下来的 $m$ 行，每行包含三个整数 $v_i, u_i, w_i$（$1 \le v_i, u_i \le n, 1 \le w_i \le 10^9, v_i \neq u_i$），表示在顶点 $v_i$ 和 $u_i$ 之间有一条权值为 $w_i$ 的边。保证图中没有自环和重边。

输出一个整数，表示给定图的子图的最大权值。

在第一个测试样例中，最优子图包含顶点 ${1, 3, 4}$，其权值为 $4 + 4 + 5 - (1 + 2 + 2) = 8$。在第二个测试样例中，最优子图为空。 由 ChatGPT 4.1 翻译