首页 > 搜索 > BFS搜索 > hdu 2433 Travel-BFS-[解题报告]C++
2014
01-26

hdu 2433 Travel-BFS-[解题报告]C++

Travel

问题描述 :

      One day, Tom traveled to a country named BGM. BGM is a small country, but there are N (N <= 100) towns in it. Each town products one kind of food, the food will be transported to all the towns. In addition, the trucks will always take the shortest way. There are M (M <= 3000) two-way roads connecting the towns, and the length of the road is 1.
      Let SUM be the total distance of the shortest paths between all pairs of the towns. Please write a program to calculate the new SUM after one of the M roads is destroyed.

输入:

      The input contains several test cases.
      The first line contains two positive integers N, M. The following M lines each contains two integers u, v, meaning there is a two-way road between town u and v. The roads are numbered from 1 to M according to the order of the input.
      The input will be terminated by EOF.

输出:

      The input contains several test cases.
      The first line contains two positive integers N, M. The following M lines each contains two integers u, v, meaning there is a two-way road between town u and v. The roads are numbered from 1 to M according to the order of the input.
      The input will be terminated by EOF.

样例输入:

5 4
5 1
1 3
3 2
5 4
2 2
1 2
1 2

样例输出:

INF
INF
INF
INF
2
2

在当时网络赛后,有一个解题报告,说这个题目的方法是暴力。具体的暴力方法是:

暴力算法:枚举每条边,然后对每个点求一次单源最短路,由于题目中的边的权值都是1,因此可以用bfs来求得每个点的单源最短路。复杂度是O(M*N*M)。由于M*N*M=3000*100*3000=9*108,不可能AC。

标程算法:仍然使用上面的思路,但要作一些预处理。对每个顶点u求一次单源最短路,把求得的结果称作u的最短路径树,并用数组记录所有点到 其他所有顶点的路径的和。若被破坏的公路不在该最短路径树上,则从u出发的所有最短路径的总和就是u到该树上的所有顶点的路径的总和,因为刚刚记录了这个 数值,因此花费O(1)时间就能返回结果。否则,删除被破坏的公路后,重新通过BFS计算从u出发的所有最短路径的总和,这步的复杂度是O(M)。由于最 短路径树上只有N-1条边,因此需要从新计算的次数只有N-1次。因此,程序的复杂度变为O(N*N*M)=3*107

存储图需要有比较适合的数据结构,才能方便地枚举边并输出答案。图的存储最好使用前向星,因为边是按顺序存放的,因此枚举边的时侯很方便。再次体会到:数据结构+算法=程序。

但是明显这个方法过于暴力。一开始没有加任何优化,这个程序跑了19XX ms,题目时限是2000 ms,几乎超时。后来将前向星里面的变量全部改成short,节省了很多内存,时间快到12XX ms。

#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;

#define N 105
#define M 6001

struct EDGE {
short b, next, id;
};
int G[N], sum[N], tot;
EDGE ET[M];
bool vv[N][M];
void addedge(int a, int b, int id) {
EDGE x = { b, G[a], id };
ET[tot] = x;
G[a] = tot++;
}

void init() {
tot = 0;
memset(G, -1, sizeof(G));
}

int n, m;
void bfs(int s) {
queue<int> Q;
bool v[N];
int x, rp, np, d = 0, i, j;
memset(v, 0, sizeof(v));
memset(vv[s], 0, sizeof(vv[s]));
Q.push(s), v[s] = 1, rp = 1,sum[s] = 0;
while (!Q.empty()) {
np = 0;
while (rp–) {
x = Q.front();
Q.pop();
sum[s] += d;
for (j = G[x]; j != -1; j = ET[j].next) {
i = ET[j].b;
if (!v[i]) {
Q.push(i);
v[i] = 1, vv[s][ET[j].id] = 1, np++;
}
}
}
rp = np, d++;
}
}

int bfs2(int s, int del) {
queue<int> Q;
bool v[N];
int x, rp, np, d = 0, i, j, ans = 0, cnt = 1;
memset(v, 0, sizeof(v));
Q.push(s), v[s] = 1, rp = 1;
while (!Q.empty()) {
np = 0;
while (rp–) {
x = Q.front();
Q.pop();
ans += d;
for (j = G[x]; j != -1; j = ET[j].next) {
if (ET[j].id == del) continue;
i = ET[j].b;
if (!v[i]) {
Q.push(i);
v[i] = 1, np++, cnt++;
}
}

}
rp = np, d++;
}
if (cnt != n) return -1;
return ans;
}

void solve() {
int i, j, a, b;
init();
for (i = 0; i < m; i++) {
scanf("%d%d", &a, &b);
addedge(a, b, i);
addedge(b, a, i);
}
for (i = 1; i <= n; i++)
bfs(i);
for (i = 0; i < 2 * m; i += 2) {
int del = i / 2, ans = 0, t;
for (j = 1; j <= n; j++) {
if (vv[j][del] == 0) ans += sum[j];
else {
t = bfs2(j, del);
if (t == -1) {
ans = -1;
break;
}
ans += t;
}
}
if (ans == -1) printf("INF\n");
else printf("%d\n", ans);
}
}
int main() {
while (~scanf("%d%d", &n, &m))
solve();
return 0;
}

解题转自:http://hi.baidu.com/novosbirsk/item/bfcf0cd201edfc2d39f6f709


  1. 我没看懂题目
    2
    5 6 -1 5 4 -7
    7 0 6 -1 1 -6 7 -5
    我觉得第一个应该是5 6 -1 5 4 输出是19 5 4
    第二个是7 0 6 -1 1 -6 7输出是14 7 7
    不知道题目例子是怎么得出来的