题目大意：
去掉给定的边，看每一个点是否能从别的点到达！
如果能够到达，则求出对于每一个点到其他所有的点最短距离之和，将这些和相加就是最后的结果
解题思路：
对每一个点求一次单源最短路，然后求和，相加的到最后的结果……
但，算一下时间复杂度： 复杂度是O(M*N*M)。由于M*N*M=3000*100*3000=9*10
8，不可能AC
所以，需要我们另辟他径。网上有说建什么最短路径树，这个我不懂……
我的思路是：引用前面的思路，对每一个点求一次最短路，并将其求和，保存在一个数组里头，定为sum[i]，i表示着一个点到所有其他点最短路之和。并将这些和相加 ans = sum[1] + …… + sum[n];
然后，删除一条边，其顶点暂定为u,v，对这条边的一个顶点u在一次求最短路，如果这个点，不能到达这条边的另一个点v，则 直接输出INF
如果，能够到达，则对v也求一次最短路，对于u，v两点来说，求得u到每一个点的最短路之和sum_u，求得v到每一个点的最短路之和sum_v，
最后结果为： ans = ans + sum_u + sum_v - sum[u] - sum[v];
ans为最后答案（千万记住是每一组的，因为有m条边）
具体看代码：
http://acm.hdu.edu.cn/showproblem.php?pid=2433时间是 953ms
1 #include <iostream>
2 #include <queue>
3 using namespace std;
4 const int SIZE = 102;
5 const int INF = 1 << 30;
6 struct node
7 {
8 int v, w, next;
9 }map[SIZE * SIZE];
10
11 int head[SIZE], use;
12 int num[SIZE * 30];
13 int sum[SIZE];
14
15 void add(int u, int v, int w)
16 {
17 map[use].v = v;
18 map[use].w = w;
19 map[use].next = head[u];
20 head[u] = use ++;
21 }
22 void init()
23 {
24 use = 0;
25 memset(head, -1, sizeof(head));
26 memset(sum, 0, sizeof(sum));
27 }
28
29 queue <int> q;
30 bool vist[SIZE];
31 int dis[SIZE];
32
33 int spfa(int s)
34 {
35 while (!q.empty()) q.pop();
36
37 for (int i = 0; i < SIZE ; i ++) dis[i] = INF;
38
39 memset(vist, false, sizeof(vist));
40 dis[s] = 0;
41 vist[s] = true;
42 q.push(s);
43 int ans = 0;
44 while (!q.empty())
45 {
46 int u = q.front();
47 q.pop();
48 vist[u] = false;
49 ans += dis[u];
50 for (int i = head[u]; i != -1; i = map[i].next)
51 {
52 int v = map[i].v;
53 if (dis[v] > dis[u] + map[i].w)
54 {
55 dis[v] = dis[u] + map[i].w;
56 if (!vist[v])
57 {
58 vist[v] = true;
59 q.push(v);
60 }
61 }
62 }
63 }
64 return ans;
65 }
66 int main()
67 {
68 int n, m;
69 while (scanf("%d%d", &n, &m) != EOF)
70 {
71 int i, j, k;
72 int u, v;
73 init();
74 memset(num, 0, sizeof(num));
75 for (i = 1; i <= m; i++)
76 {
77 scanf("%d%d", &u, &v);
78 num[i] = use;
79 add(u, v, 1);
80 add(v, u, 1);
81 }
82 int ans = 0;
83 for (i = 1; i <= n; i++)
84 {
85 sum[i] = spfa(i);
86 ans += sum[i];
87 }
88 int tmp = ans;
89 for (i = 1; i <= m; i++)
90 {
91 map[num[i]].w = INF;
92 map[num[i]^1].w = INF;
93
94 ans = tmp;
95 ans += spfa(map[num[i]].v);
96
97 if (dis[map[num[i]^1].v] == INF)
98 {
99 printf("INF\n");
100 }
101 else
102 {
103 ans += spfa(map[num[i]^1].v);
104 ans = ans - sum[map[num[i]].v] - sum[map[num[i]^1].v];
105 printf("%d\n", ans);
106 }
107 map[num[i]].w = 1;
108 map[num[i]^1].w = 1;
109 }
110 }
111 return 0;
112 }
113
posted on 2012-03-09 15:35
路修远 阅读(1849)
评论(8) 编辑 收藏 引用 所属分类:
路修远