题意：不想说，这个题意思了，含糊不清=-= Dijkstra算法，无法计算有负边的图，原因是有负边的图存在是会打乱Dijkstra算法的前提，当前优先队列取出点的距离为起点到该点的最小距离，因为如果后面有负边这个距离会更小。除此之外Bellman-Ford算法和Floyd-warshall算法都可以计算有负边的图，且判断是否有负圈。Floyd-Warshall算法：该算法用到了动态规划归约的思想来求任意两点间的最短距离。令：d[k][i][j]为最短路可以包括0到k的所有顶点时i到j的最短距离，那么做一个归约为从0到k – 1的所有顶点中选择最短路，，并且考虑是否包含第k个顶点的两种情况中最小的，即：。;int d[311][311], n, m, par[311], rank[311], team[311];void get_team(void) {for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {if (i == j) d[i][j] = 0;else d[i][j] = 0x3fffff;}}for (int i = 0; i < m; i++) {int x;scanf(“%d”, &x);for (int j = 0; j < x; j++) {scanf(“%d”, &team[j]);}for (int j = 0; j < x; j++) {for (int k = j + 1; k < x; k++) {if (team[k] == team[j]) continue;d[team[k] – 1][team[j] – 1] = 1;d[team[j] – 1][team[k] – 1] = 1;}}}}void Floyd_Warshall(void) {for (int i = 0; i < n; i++)for (int j = 0; j < n; j++)for(int k = 0; k < n; k++) d[j][k] = min(d[j][k], d[j][i] + d[i][k]);}int average_max(void) {int max = 0x3fffff;for (int i = 0; i < n; i++) {int temp = 0;for (int j = 0; j < n; j++) {temp += d[i][j];}if(temp < max) swap(max, temp);}return max * 100 / (n – 1);}int main(void) {while (~scanf(“%d%d”, &n, &m)) {get_team();Floyd_Warshall();printf(“%d\n”,(int)average_max());}return 0;}
贪婪是最真实的贫穷，满足是最真实的财富
