图论相关习题
题目链接
@[toc]
Floyd
A Calling Circles
题意：如果两个人互相打电话（直接或者间接），则说他们在同一个电话圈里。例如，a打给b，b打给c，c打给d，d打给a，则这四个人在同一个圈里；如果e打给f，而f不打给e，则不能推出e和f在同一个电话圈。输入$n(n\leq 25)$个人的m 次电话，找出所有的电话圈。人名只包含字母，不超过25个字符，且不重复。
感谢@UKE自动机 提供的翻译
题目要求有向图里的所有环，并且两个环如果有交点则视为同一个环。
- 首先，求有向图的可达矩阵，采用Floyd-Warshall算法。
- 如果在有向图内，由A点可达B点，由B点也可达A点，则说明A，B两点在同一个环内。
- 在可达矩阵上遍历求解即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
using namespace std;
int n, m;
//key=名字，int=编号
map<string, int> getNode;
//key=编号，int=名字
map<int, string> getName;
//可达矩阵
int Matrix[25][25];
bool Visted[26]{ false };
//为每个名字设置一个不同的编号
inline int setHash(const string&Name,int&cnt) {
auto&& it = getNode.find(Name);
if (it == getNode.end()) {
getNode[Name] = cnt;
getName[cnt] = Name;
++cnt;
return cnt - 1;
}
else {
return it->second;
}
}
inline bool input() {
cin >> n >> m;
if (!n && !m) {
return false;
}
getNode.clear();
getName.clear();
int&& cnt = 0;
memset(Matrix, 0x0, sizeof(Matrix));
while (m--) {
string from, to;
cin >> from >> to;
int
&& FromNode = setHash(from, cnt),
&& ToNode = setHash(to, cnt);
//由From可达于to
Matrix[FromNode][ToNode] = 1;
}
return true;
}
//求可达矩阵
void Floyd() {
for (int k = 0; k < n; ++k) {
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
Matrix[i][j] = Matrix[i][k] && Matrix[k][j] || Matrix[i][j];
}
}
}
}
void DFS(int i,bool isFirstDFS) {
Visted[i] = true;
if (!isFirstDFS) {
cout << ", ";
}
cout << getName[i];
for (int j = 0; j < n; ++j) {
if (
!Visted[j]&&
Matrix[i][j] &&
Matrix[j][i]
) {
DFS(j,false);
break;
}
}
}
int main() {
int&& Cnt = 0;
while (input()) {
Floyd();
memset(Visted, false, sizeof(Visted));
printf("Calling circles for data set %d:\n", ++Cnt);
for (int i = 0; i < n; ++i) {
if (!Visted[i]) {
DFS(i,true);
cout << endl;
}
}
}
return 0;
}
B - Audiophobia
题意翻译题意描述有一张有C个路口，S条街道的无向图，每条街道都一个噪音值。请问从$c_1$走到$c_2$，经过的路径上最大噪音的最小值是多少。
输入格式
输入包含多组数据，每组数据第一行包含三个整数$C\leq 100,S\leq1,000,Q\leq 10,000$，分别表示路口数、街道数、询问数。接下来S行，每行3个整数$c_1,c_2,d(c_1≠c_2)$，分别表示一条街道连接的两个路口编号，以及这条街道噪音的分贝值。接下来Q行，每行给定两个路口编号$c_1,c_2(c_1 ≠ c_2)$)，请你输出这两个路口之间路径的最大分贝值的最小值。如果$c_1$不能到达$c_2$，输出”no path“。输入以C=S=Q=0结束。
输出格式
每组数据前输出一行数据组数的编号。（见样例）对于每个询问，输出一行。每两组数据之间输出一个空行。
1 |
|
C Say Cheese
题意翻译 无限大的奶酪里有$n (0≤n≤100)$ 个球形的洞。你的任务是帮助小老鼠 A 用最短的时间到达小老鼠 O 所在位置。奶酪里的移动速度为 10 秒一个单位，但是在洞里可以瞬间移动。洞和洞可以相交。输入 n 个球的位置和半径，以及 A 和 O 的坐标，求最短时间。
裸的多源最短路1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
using namespace std;
double Map[101][101];
struct Node {
double x, y, z, r;
Node(double x, double y, double z, double r) :x(x), y(y), z(z), r(r) { }
Node() = default;
double getSquare(double&& x)const {
return x * x;
}
double getDis(const Node& Right)const {
double&& Dis = sqrt(
getSquare(x - Right.x) +
getSquare(y - Right.y) +
getSquare(z - Right.z)
);
Dis -= r + Right.r;
if (Dis <= 0.) {
return 0.;
}
else {
return Dis;
}
}
}nodes[103];
int n;
bool input() {
cin >> n;
if (n == -1) {
return false;
}
for (int i = 1; i <= n; ++i) {
double x, y, z, r;
cin >> x >> y >> z >> r;
nodes[i] = Node(x, y, z, r);
}
auto initPoint = [](Node nodes[103], int index)->void {
double x, y, z;
cin >> x >> y >> z;
nodes[index] = Node(x, y, z, 0.);
};
initPoint(nodes, n + 1);
initPoint(nodes, n + 2);
for (int i = 1; i <= n + 2; ++i) {
for (int j = 1; j <= n + 2; ++j) {
Map[i][j] = nodes[i].getDis(nodes[j]);
}
}
return true;
}
void Floyd() {
for (int k = 1; k <= n + 2; ++k) {
for (int i = 1; i <= n + 2; ++i) {
for (int j = 1; j <= n + 2; ++j) {
Map[i][j] = min(Map[i][j], Map[i][k] + Map[k][j]);
}
}
}
}
int main() {
int cnt = 0;
while (input()) {
Floyd();
printf("Cheese %d: Travel time = %.0f sec\n", ++cnt, round(Map[n + 1][n + 2] * 10.));
}
return 0;
}
