#include <stdio.h> #include <stdlib.h> #define MAX_N 10000 #define MOD 100007 int n, A[MAX_N][MAX_N], visited[MAX_N], dist[MAX_N]; int prim() { int i, j, k, minDist, ans = 0; for (i = 0; i < n; i++) { visited[i] = 0; dist[i] = A[0][i]; } visited[0] = 1; for (i = 1; i < n; i++) { minDist = -1; for (j = 0; j < n; j++) { if (!visited[j] && (minDist == -1 || dist[j] < minDist)) { minDist = dist[j]; k = j; } } visited[k] = 1; ans = (ans + minDist) % MOD; for (j = 0; j < n; j++) { if (!visited[j] && A[k][j] != -1 && (dist[j] == -1 || A[k][j] < dist[j])) { dist[j] = A[k][j]; } } } return ans; } int main() { int i, j; scanf("%d", &n); for (i = 0; i < n; i++) { for (j = 0; j < n; j++) { scanf("%d", &A[i][j]); } } printf("%d\n", prim()); return 0; }

这段代码和我上一条回答中给出的代码是一模一样的，只是没有把最后的输出语句改成了“最小生成树的边权值之和与100007取模”。因此，如果输入为“3 -1 1 1 1 -1 1 1 1 -1”，这段代码的输出应该是“2”，而不是“2\n”。如果要实现最后的取模操作，只需要在输出语句中修改一下即可，如下所示：

printf("%d\n", prim() % MOD);

这样就可以得到最小生成树的边权值之和与100007取模的结果了。