題目大意：
去掉給定的邊，看每一個點是否能從別的點到達！
如果能夠到達，則求出對于每一個點到其他所有的點最短距離之和，將這些和相加就是最后的結(jié)果
解題思路：
對每一個點求一次單源最短路，然后求和，相加的到最后的結(jié)果……
但，算一下時間復(fù)雜度： 復(fù)雜度是O(M*N*M)。由于M*N*M=3000*100*3000=9*10
8，不可能AC
所以，需要我們另辟他徑。網(wǎng)上有說建什么最短路徑樹，這個我不懂……
我的思路是：引用前面的思路，對每一個點求一次最短路，并將其求和，保存在一個數(shù)組里頭，定為sum[i]，i表示著一個點到所有其他點最短路之和。并將這些和相加 ans = sum[1] + …… + sum[n];
然后，刪除一條邊，其頂點暫定為u,v，對這條邊的一個頂點u在一次求最短路，如果這個點，不能到達這條邊的另一個點v，則 直接輸出INF
如果，能夠到達，則對v也求一次最短路，對于u，v兩點來說，求得u到每一個點的最短路之和sum_u，求得v到每一個點的最短路之和sum_v，
最后結(jié)果為： 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
路修遠 閱讀(1945)
評論(8) 編輯 收藏 引用 所屬分類:
路修遠