建设项目环境影响登记网站天津,网站建设课程中的收获,百度网站制作,加强网站备案管理算法提高课笔记#xff09; 文章目录 例题牛的旅行题意思路代码 排序题意思路代码 观光之旅题意思路代码 例题
牛的旅行
原题链接
农民John的农场里有很多牧区#xff0c;有的路径连接一些特定的牧区。
一片所有连通的牧区称为一个牧场。
但是就目前而言#xff0c;你…算法提高课笔记 文章目录 例题牛的旅行题意思路代码 排序题意思路代码 观光之旅题意思路代码 例题
牛的旅行
原题链接
农民John的农场里有很多牧区有的路径连接一些特定的牧区。
一片所有连通的牧区称为一个牧场。
但是就目前而言你能看到至少有两个牧区不连通。
现在John想在农场里添加一条路径注意恰好一条。
一个牧场的直径就是牧场中最远的两个牧区的距离本题中所提到的所有距离指的都是最短的距离。
考虑如下的两个牧场每一个牧区都有自己的坐标
图 1 是有 5 个牧区的牧场牧区用“*”表示路径用直线表示。
图 1 所示的牧场的直径大约是 12.07106, 最远的两个牧区是 A 和 E它们之间的最短路径是 A-B-E。
图 2 是另一个牧场。
这两个牧场都在John的农场上。
John将会在两个牧场中各选一个牧区然后用一条路径连起来使得连通后这个新的更大的牧场有最小的直径。
注意如果两条路径中途相交我们不认为它们是连通的。
只有两条路径在同一个牧区相交我们才认为它们是连通的。
现在请你编程找出一条连接两个不同牧场的路径使得连上这条路径后所有牧场生成的新牧场和原有牧场中直径最大的牧场的直径尽可能小。
输出这个直径最小可能值。
输入格式
第 1 行一个整数 N, 表示牧区数
第 2 到 N1 行每行两个整数 X,Y 表示 N 个牧区的坐标。每个牧区的坐标都是不一样的。
第 N2 行到第 2*N1 行每行包括 N 个数字 ( 0或1 ) 表示一个对称邻接矩阵。
例如题目描述中的两个牧场的矩阵描述如下 A B C D E F G H
A 0 1 0 0 0 0 0 0
B 1 0 1 1 1 0 0 0
C 0 1 0 0 1 0 0 0
D 0 1 0 0 1 0 0 0
E 0 1 1 1 0 0 0 0
F 0 0 0 0 0 0 1 0
G 0 0 0 0 0 1 0 1
H 0 0 0 0 0 0 1 0输入数据中至少包括两个不连通的牧区。
输出格式
只有一行包括一个实数表示所求答案。
数字保留六位小数。
数据范围 1 ≤ N ≤ 150 , 1≤N≤150, 1≤N≤150, 0 ≤ X , Y ≤ 105 0≤X,Y≤105 0≤X,Y≤105
输入样例
8
10 10
15 10
20 10
15 15
20 15
30 15
25 10
30 10
01000000
10111000
01001000
01001000
01110000
00000010
00000101
00000010输出样例
22.071068题意
给出一张图连通的部分算作一个区域每个区域的直径为区域中相隔最远的两个点的距离问在不同区域中添加一条边得到的最小直径是多少
思路
先建图然后跑一遍floyd算出和每一个点相隔最远的点的距离
得到的最新直径一定大于等于原来的最大直径因此可以先求出原来的最大直径maxd[i]
加上一条边[i, j]得到的新直径是maxd[i] maxd[j] dist[i][j]
二者取最大值即可
代码
#include bits/stdc.husing namespace std;typedef pairdouble, double PDD;const int N 155;
const double INF 1e20;int n;
double d[N][N];
double maxd[N];
char g[N][N];
PDD q[N];double get_dist(PDD a, PDD b)
{double dx a.first - b.first;double dy a.second - b.second;return sqrt(dx * dx dy * dy);
}int main()
{cin n;for (int i 0; i n; i ) cin q[i].first q[i].second;for (int i 0; i n; i ) cin g[i];for (int i 0; i n; i )for (int j 0; j n; j )if (i j) d[i][j] 0;else if (g[i][j] 1) d[i][j] get_dist(q[i], q[j]); // ij之间有边else d[i][j] INF; // ij之间无边// floyd更新最短路for (int k 0; k n; k )for (int i 0; i n; i )for (int j 0; j n; j )d[i][j] min(d[i][j], d[i][k] d[k][j]);double r1 0; // 两个牧场中最长的直径for (int i 0; i n; i ){for (int j 0; j n; j )if (d[i][j] INF / 2) // 说明ij之间有边maxd[i] max(maxd[i], d[i][j]); // 更新与i最远的点距离r1 max(r1, maxd[i]); // 更新直径}double r2 INF; // 加边之后的最长值for (int i 0; i n; i )for (int j 0; j n; j )if (d[i][j] INF / 2) // 说明ij之间无边 可以加边r2 min(r2, maxd[i] maxd[j] get_dist(q[i], q[j]));printf(%.6lf\n, max(r1, r2));
}排序
原题链接
给定 n 个变量和 m 个不等式。其中 n 小于等于 26变量分别用前 n 的大写英文字母表示。
不等式之间具有传递性即若 AB 且 BC则 AC。
请从前往后遍历每对关系每次遍历时判断
如果能够确定全部关系且无矛盾则结束循环输出确定的次序 如果发生矛盾则结束循环输出有矛盾 如果循环结束时没有发生上述两种情况则输出无定解。
输入格式
输入包含多组测试数据。
每组测试数据第一行包含两个整数 n 和 m。
接下来 m 行每行包含一个不等式不等式全部为小于关系。
当输入一行 0 0 时表示输入终止。
输出格式
每组数据输出一个占一行的结果。
结果可能为下列三种之一
如果可以确定两两之间的关系则输出 Sorted sequence determined after t relations: yyy...y.,其中t指迭代次数yyy...y是指升序排列的所有变量。如果有矛盾则输出 Inconsistency found after t relations.其中t指迭代次数。如果没有矛盾且不能确定两两之间的关系则输出 Sorted sequence cannot be determined.。
数据范围 2 ≤ n ≤ 26 变量只可能为大写字母 A ∼ Z 。 2≤n≤26变量只可能为大写字母 A∼Z。 2≤n≤26变量只可能为大写字母A∼Z。
输入样例1
4 6
AB
AC
BC
CD
BD
AB
3 2
AB
BA
26 1
AZ
0 0输出样例1
Sorted sequence determined after 4 relations: ABCD.
Inconsistency found after 2 relations.
Sorted sequence cannot be determined.输入样例2
6 6
AF
BD
CE
FD
DE
EF
0 0输出样例2
Inconsistency found after 6 relations.输入样例3
5 5
AB
BC
CD
DE
EA
0 0输出样例3
Sorted sequence determined after 4 relations: ABCDE.题意
从前到后遍历给出的关系如果能确定所有关系就直接输出当前次数和关系如果前后矛盾则输出矛盾如果得不到最终关系就输出得不到最终关系
思路
传递闭包
已知ab bc 一定可以推出 ac根据这个性质我们可以在得到每个新的判断时进行传递看看是否不满足原先已知的结论如果不满足就会出现i和i的关系确定的结果
代码
#include bits/stdc.husing namespace std;const int N 26;int n, m;
bool g[N][N], d[N][N]; // 表示两个字母之间关系前一个字母小于后一个字母是否确定
bool st[N];void floyd()
{memcpy(d, g, sizeof d);for (int k 0; k n; k )for (int i 0; i n; i )for (int j 0; j n; j )d[i][j] | d[i][k] d[k][j]; // 如果有i-k k-j的边 那就加上i-j的边
}int check()
{for (int i 0; i n; i )if (d[i][i]) return 2; // 出现矛盾返回2for (int i 0; i n; i )for (int j 0; j i; j )if (!d[i][j] !d[j][i])return 0; // 遍历所有数对 没确定返回0return 1; // 确定就返回1
}char get_min()
{for (int i 0; i n; i )if (!st[i]){bool flag true;for (int j 0; j n; j )if (!st[j] d[j][i]) // 如果有没出现过的j比i还小的话说明i不是最小值{flag false;break;}if (flag) // 否则i就是当前没出现过的数中的最小值{st[i] true;return A i;}}
}int main()
{while (cin n m, n || m){memset(g, 0, sizeof g);int type 0, t; // type表示目前关系未确定/确定/矛盾for (int i 1; i m; i ){char str[5];cin str;int a str[0] - A, b str[2] - A;if (!type){g[a][b] 1;floyd();type check();if (type) t i; // t记录经过几次才确定所有关系}}if (!type) puts(Sorted sequence cannot be determined.); // 关系不确定else if (type 2) cout Inconsistency found after t relations.\n; // 矛盾else // 确定{memset(st, 0, sizeof st);cout Sorted sequence determined after t relations: ;for (int i 0; i n; i ) cout get_min();cout .\n;}}
}观光之旅
原题链接
给定一张无向图求图中一个至少包含 3 个点的环环上的节点不重复并且环上的边的长度之和最小。
该问题称为无向图的最小环问题。
你需要输出最小环的方案若最小环不唯一输出任意一个均可。
输入格式
第一行包含两个整数 N 和 M表示无向图有 N 个点M 条边。
接下来 M 行每行包含三个整数 uvl表示点 u 和点 v 之间有一条边边长为 l。
输出格式
输出占一行包含最小环的所有节点按顺序输出如果不存在则输出 No solution.。
数据范围 1 ≤ N ≤ 100 , 1≤N≤100, 1≤N≤100, 1 ≤ M ≤ 10000 , 1≤M≤10000, 1≤M≤10000, 1 ≤ l 500 1≤l500 1≤l500
输入样例
5 7
1 4 1
1 3 300
3 1 10
1 2 16
2 3 100
2 5 15
5 3 20输出样例
1 3 5 2题意
无向图的最小环裸题
思路
假设环的形式是这样的ij均小于k 那么环的长度就是d[i][j] g[j][k] g[k][i]d代表ij在图上的最短距离g表示两点之间有边的话 边的长度
用pos[i][j] k记录i和j的最短路由k的状态转移k是路径中编号最大的点
在floyd中循环每个k如果d[i][j] g[j][k] g[k][i]比当前的最小环长度更小就更新一下
使用类似中序遍历的算法求出环中的字母
代码
#include bits/stdc.husing namespace std;typedef long long ll;const int N 110, INF 0x3f3f3f3f;int n, m;
int d[N][N], g[N][N];
int pos[N][N];
int path[N], cnt;void get_path(int i, int j)
{if (pos[i][j] 0) return;// 类似于中序遍历int k pos[i][j];get_path(i, k);path[cnt ] k;get_path(k, j);
}int main()
{cin n m;memset(g, 0x3f3f3f3f, sizeof g);for (int i 1; i n; i ) g[i][i] 0; // 避免统计自环while (m -- ){int a, b, c;cin a b c;g[a][b] g[b][a] min(g[a][b], c);}int res INF;memcpy(d, g, sizeof d);for (int k 1; k n; k ){for (int i 1; i k; i )for (int j i 1; j k; j )if ((ll)d[i][j] g[j][k] g[k][i] res) // 一旦发现比原来的最短路还要短的路径就更新{res d[i][j] g[j][k] g[k][i]; // 最短路长度// 更新最短路中的点cnt 0;path[cnt ] k;path[cnt ] i;get_path(i, j);path[cnt ] j;}// 更新两点之间的距离 在更新完最小环之后更新所以不会对最小环有影响for (int i 1; i n; i )for (int j 1; j n; j )if (d[i][j] d[i][k] d[k][j]){d[i][j] d[i][k] d[k][j];pos[i][j] k;}}if (res INF) puts(No solution.);else{for (int i 0; i cnt; i ) cout path[i] ;cout \n;}
}
