本文主要是介绍HDU - 2433 Travel（BFS+思维），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2433
Problem Description
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.
Input
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.
Output
Output M lines, the i-th line is the new SUM after the i-th road is destroyed. If the towns are not connected after the i-th road is destroyed, please output “INF” in the i-th line.
Sample Input
5 4
5 1
1 3
3 2
5 4
2 2
1 2
1 2
Sample Output
INF
INF
INF
INF
2
2
题目描述感觉有点缺漏，要求的输出是每个点到其它点的距离之和的和，而不是仅仅是每一对。
先是得预处理，让每个点BFS求到各个其它的路径和记为sum[i]，顺便用used[i][u][v]来记录路径。
主要就是分情况讨论：1.原图就不是连通图，直接输出M个INF，2.删除边(u,v)，遍历每一个点i，1）如果(used[i][u][v]||used[i][v][u]为真)，则重新对该点bfs，六个出现非连通图直接跳出并输出INF，否则ans加上新值，2）used为假，ans加上原值sum[i]。
代码如下：
#include<cstdio>
#include<vector>
#include<queue>
#include<map>
using namespace std;int N, M, sum[105], used[105][105][105];struct edge {int from, to;
}del[3005];vector<int>e[105];struct node {int id, dis;node(int x, int d) :id(x), dis(d) {}
};int bfs(int s, bool init) {int ret = 0;bool vised[105] = { 0 };vised[s] = true;queue<node>q;q.push(node(s, 0));while (!q.empty()) {node u = q.front(); q.pop();ret += u.dis;for (int i = 0; i < e[u.id].size(); i++) {int x = e[u.id][i];if (vised[x])continue;vised[x] = true;if (init)used[s][u.id][x] = 1;q.push(node(x, u.dis + 1));}}for (int i = 1; i <= N; i++)if (!vised[i])return -1;return ret;
}int main(void) {while (~scanf("%d %d", &N, &M)) {for (int i = 1; i <= N; i++)e[i].clear();for (int i = 1; i <= M; i++) {int u, v;scanf("%d %d", &u, &v);del[i].from = u, del[i].to = v;e[u].push_back(v);e[v].push_back(u);}bool isInf = false;for (int i = 1; i <= N; i++) {sum[i] = bfs(i, true);if (sum[i] == -1)isInf = true;}if (isInf) {for (int i = 1; i <= M; i++)printf("INF\n"); continue;}for (int k = 1; k <= M; k++) {int ans = 0, u = del[k].from, v = del[k].to;for (int i = 0; i < e[u].size(); i++)if (e[u][i] == v) {e[u].erase(e[u].begin() + i); break;}for (int i = 0; i < e[v].size(); i++)if (e[v][i] == u) {e[v].erase(e[v].begin() + i); break;}for (int i = 1; i <= N; i++) {if (used[i][u][v] || used[i][v][u]) {int tmp = bfs(i, false);if (tmp == -1) {isInf = true; break;}else ans += tmp;}else ans += sum[i];}e[u].push_back(v);e[v].push_back(u);if (isInf) {printf("INF\n"); isInf = false;}else printf("%d\n", ans);}}return 0;
}
这篇关于HDU - 2433 Travel（BFS+思维）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
