问题 A: 图的最小生成树-Prim算法
题目描述
Prim算法是求解带权图的最小生成树的经典算法。其步骤如下：
E1：任取一个顶点构成U={v0}；构造向量cost[0…n-1]和adj[0…n-1]，cost[i]表示顶点vi到U的最短边的长度，adj[i]表示顶点vi到U的最短边在U中的邻接点的下标；其中，vi∈V-U。初始时，生成树T为空集。
E2：重复n-1次
E21：从V-U中选出cost值最小的顶点vk，将边<vk, vadj[k]>加入到生成树T中，然后将vk并入U中；
E22：修正V-U中各顶点的cost值和adj值；
本题要求根据Prim算法，求解第一步状态下的cost和adj两个向量。
输入格式
输入为邻接矩阵存储的图，第一行为正整数n（小于100），表示图中顶点个数
接下来是n行，每行为n个空格隔开的非负整数。0表示两个顶点之间没有直达边，非0表示有直达边。且该数字为对应直达边的权重。
输出格式
假设第一步选择将序号最小的0号节点并入集合U。按照样例格式输出cost和adj两个向量
输入样例 复制
7
0 10 9 13 0 0 0
10 0 0 15 7 0 12
9 0 0 4 0 3 0
13 15 4 0 0 22 23
0 7 0 0 0 0 20
0 0 3 22 0 0 32
0 12 0 23 20 32 0
输出样例 复制
0 - -
1 10 0
2 9 0
3 13 0
4 - -
5 - -
6 - -
AC代码：
#include <bits/stdc++.h>
using namespace std;
int main(){
int n;
cin>>n;
int matrix[n+5][n+5];
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
cin>>matrix[i][j];
if(!i){
if(matrix[i][j])
printf("%d %d 0\n",j,matrix[i][j]);
else printf("%d - -\n",j);
}
}
}
return 0;
}
问题 B: 图的最小生成树-Kruskal算法
题目描述
Kruskal算法是最小生成树的经典算法，其步骤为：
E1：将所有的边按权值排序；
E2：设每个顶点为一个独立的点集，生成树T为空集；
E3：依序扫描每一条边<vi,vj>，直到已输出n-1条边：
E31：若vi、vj不在同一点集中，则将该边加入生成树T中，并合并这两个点集；否则舍弃该边；
本题要求读入带权图，对其所有边按权值排序后输出。
输入格式
输入为邻接矩阵存储的图，第一行为正整数n（小于100），表示图中顶点个数
接下来是n行，每行为n个空格隔开的非负整数。0表示两个顶点之间没有直达边，非0表示有直达边。且该数字为对应直达边的权重。
输出格式
对所有边按权重排序后输出。如果图只有1个点（即没有边），则直接输出空行。
输入样例 复制
7
0 10 9 13 0 0 0
10 0 0 15 7 0 12
9 0 0 4 0 3 0
13 15 4 0 0 22 23
0 7 0 0 0 0 20
0 0 3 22 0 0 32
0 12 0 23 20 32 0
输出样例 复制
<2,5>:3
<5,2>:3
<3,2>:4
<2,3>:4
<4,1>:7
<1,4>:7
<2,0>:9
<0,2>:9
<1,0>:10
<0,1>:10
<1,6>:12
<6,1>:12
<0,3>:13
<3,0>:13
<1,3>:15
<3,1>:15
<4,6>:20
<6,4>:20
<3,5>:22
<5,3>:22
<6,3>:23
<3,6>:23
<5,6>:32
<6,5>:32
数据范围与提示
注意题目的测试数据构造时用的排序算法如下：
for(int i=0;i<n;i++)
for(int j=i+1;j<n;j++)
if(a[j]<a[i]) swap(i,j); // 交换
AC代码：
#include <bits/stdc++.h>
using namespace std;
struct node{
int start,end,val;
};
int cmp(struct node a,struct node b){
return a.val<b.val;
}
int main(){
int n;
cin>>n;
int matrix[n+5][n+5],top=0;
struct node a[n+5];
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
cin>>matrix[i][j];
if(matrix[i][j]){
a[top].start=i;a[top].end=j;a[top].val=matrix[i][j];
top++;
}
}
}
//sort(a,a+top,cmp);
for(int i=0;i<top;i++){
for(int j=i+1;j<top;j++){
if(a[j].val<a[i].val){
struct node b;
b.start=a[i].start;b.end=a[i].end;b.val=a[i].val;
a[i].start=a[j].start;a[i].end=a[j].end;a[i].val=a[j].val;
a[j].start=b.start;a[j].end=b.end;a[j].val=b.val;
}
}
}
for(int i=0;i<top;i++){
printf("<%d,%d>:%d\n",a[i].start,a[i].end,a[i].val);
}
if(n==1)printf("\n");
return 0;
}
问题 C: 算法7-9：最小生成树
题目描述
最小生成树问题是实际生产生活中十分重要的一类问题。假设需要在n个城市之间建立通信联络网，则连通n个城市只需要n-1条线路。这时，自然需要考虑这样一个问题，即如何在最节省经费的前提下建立这个通信网。
可以用连通网来表示n个城市以及n个城市之间可能设置的通信线路，其中网的顶点表示城市，边表示两个城市之间的线路，赋于边的权值表示相应的代价。对于n个顶点的连通网可以建立许多不同的生成树，每一棵生成树都可以是一个通信网。现在，需要选择一棵生成树，使总的耗费最小。这个问题就是构造连通网的最小代价生成树，简称最小生成树。一棵生成树的代价就是树上各边的代价之和。
在本题中，读入一个无向图的邻接矩阵（即数组表示），建立无向图并按照以上描述中的算法建立最小生成树，并输出最小生成树的代价。
输入格式
输入的第一行包含一个正整数n，表示图中共有n个顶点。其中n不超过50。 以后的n行中每行有n个用空格隔开的整数，对于第i行的第j个整数，如果不为0，则表示第i个顶点和第j个顶点有直接连接且代价为相应的值，0表示没有直接连接。当i和j相等的时候，保证对应的整数为0。 输入保证邻接矩阵为对称矩阵，即输入的图一定是无向图，且保证图中只有一个连通分量。
输出格式
只有一个整数，即最小生成树的总代价。请注意行尾输出换行。
输入样例 复制
4
0 2 4 0
2 0 3 5
4 3 0 1
0 5 1 0
输出样例 复制
6
AC代码：
#include <bits/stdc++.h>
using namespace std;
struct node{
int cost,adj;
};
int main(){
int n;
cin>>n;
int matrix[n+5][n+5];
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
cin>>matrix[i][j];
}
}
int totalcost=0,cost[n],adj[n];
cost[0]=-1;adj[0]=0;
for(int i=1;i<n;i++){//初始化
cost[i]=matrix[0][i];
adj[i]=0;
}
for(int i=1;i<n;i++){
int minicost=INFINITY,k=0;
for(int j=1;j<n;j++){
if(cost[j]>0&&cost[j]<minicost){
minicost=cost[j];
k=j;
}
}
totalcost+=minicost;
//printf("minicost=%d k=%d\n",minicost,k);
cost[k]=-1;
for(int j=1;j<n;j++){
if(cost[j]>0&&matrix[k][j]&&matrix[k][j]<cost[j]){
cost[j]=matrix[k][j];
adj[j]=k;
}else if(cost[j]==0&&matrix[k][j]){
cost[j]=matrix[k][j];
adj[j]=k;
}
}
// for(int m=0;m<n;m++)printf("index=%d cost=%d adj=%d\n",m,cost[m],adj[m]);
// printf("\n");
}
cout<<totalcost;
return 0;
}
问题 D: 算法7-15：迪杰斯特拉最短路径算法
题目描述
在带权有向图G中，给定一个源点v，求从v到G中的其余各顶点的最短路径问题，叫做单源点的最短路径问题。
在常用的单源点最短路径算法中，迪杰斯特拉算法是最为常用的一种，是一种按照路径长度递增的次序产生最短路径的算法。
可将迪杰斯特拉算法描述如下：
设辅助向量u[0…n-1]、shortest[0…n-1]和path[0…n-1]；u[i]为１表示从v0到vi的最短路径已经求出，为０表示尚未求出；shortest[i]记录目前已知的从v0到vi的较短路径的长度；path[i]记录目前已知的从v0到vi的较短路径；
初始时，设置从v0到vi的直达弧为目前已知的较短路径；
E1：初始化辅助向量u、shortest、path；
E2：循环n-1次：
E21：从M-U中选择最小的shortest[k]；
E22：将vk并入Ｕ中;
E23：对M-U中的各顶点vi的已知较短路径进行修正：若P0,k+{i}的长度短于目前已知的P0,i的长度，则用P0,k+{i}取代原P0,i；
在本题中，读入一个有向图的带权邻接矩阵（即数组表示），建立有向图并按照以上描述中的算法求出源点至每一个其它顶点的最短路径长度。
输入格式
输入的第一行包含2个正整数n和s，表示图中共有n个顶点，且源点为s。其中n不超过50，s小于n。 以后的n行中每行有n个用空格隔开的整数。对于第i行的第j个整数，如果大于0，则表示第i个顶点有指向第j个顶点的有向边，且权值为对应的整数值；如果这个整数为0，则表示没有i指向j的有向边。当i和j相等的时候，保证对应的整数为0。
输出格式
只有一行，共有n-1个整数，表示源点至其它每一个顶点的最短路径长度。如果不存在从源点至相应顶点的路径，输出-1。 请注意行尾输出换行。
输入样例 复制
4 1
0 3 0 1
0 0 4 0
2 0 0 0
0 0 1 0
输出样例 复制
6 4 7
AC代码：
#include <bits/stdc++.h>
using namespace std;
struct node {
int shortest, path;
};
int main() {
int n, b;
cin >> n >> b;
int martrix[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> martrix[i][j];
}
}
struct node a[n];
for (int i = 0; i < n; i++) { //初始化
a[i].path = b;
a[i].shortest = martrix[b][i];
}
a[b].shortest=-1;
int answer[n];
memset(answer,0,sizeof(answer));
for (int i = 0; i < n-1 ; i++) {
int minn = INFINITY, indexmin = -1;
for (int j = 0; j < n; j++) { //寻找最小值
if (a[j].shortest > 0 && minn > a[j].shortest) {
minn = a[j].shortest;
indexmin = j;
}
}
answer[indexmin] = minn; //最小值进入answer
a[indexmin].shortest = -1;//-1为已遍历的结点
// printf("************************\nshortest=");
// for(int j=0;j<n;j++){
// printf("%d ",a[j].shortest);
// }
// printf("\npath=");
// for(int j=0;j<n;j++){
// printf("%d ",a[j].path);
// }
// printf("\n");
// printf("answer=");
// for(int j=0;j<n;j++)printf("%d ",answer[j]);
// printf("\n");
// printf("minn=%d indexmin=%d\n",minn,indexmin);
//更新a
for (int j = 0; j < n; j++) {
if (martrix[indexmin][j]) {
if (a[j].shortest == 0 ||
a[j].shortest > 0 && minn + martrix[indexmin][j] < a[j].shortest) {
a[j].shortest = minn + martrix[indexmin][j];
a[j].path = indexmin;
}
}
}
}
for (int i = 0; i < n; i++) {
if (i != b) {
cout << answer[i] << " ";
}
}
return 0;
}
问题 E: 算法7-16：弗洛伊德最短路径算法
题目描述
在带权有向图G中，求G中的任意一对顶点间的最短路径问题，也是十分常见的一种问题。
解决这个问题的一个方法是执行n次迪杰斯特拉算法，这样就可以求出每一对顶点间的最短路径，执行的时间复杂度为O(n3)。
而另一种算法是由弗洛伊德提出的，时间复杂度同样是O(n3)，但算法的形式简单很多。
可以将弗洛伊德算法描述如下：
E1：初始化从vi到vj的目前已知较短路径为从vi到vj的直达弧；
E2：对每两顶点对(vi,vj)依次计算P(i,j,k)，k=0…n-1，计算规则为：P(i,j,k) = min(P(i,k,k-1) + P(k,j,k-1), P(i,j,k-1))
在本题中，读入一个有向图的带权邻接矩阵（即数组表示），建立有向图并按照以上描述中的算法求出每一对顶点间的最短路径长度。
输入格式
输入的第一行包含1个正整数n，表示图中共有n个顶点。其中n不超过50。 以后的n行中每行有n个用空格隔开的整数。对于第i行的第j个整数，如果大于0，则表示第i个顶点有指向第j个顶点的有向边，且权值为对应的整数值；如果这个整数为0，则表示没有i指向j的有向边。当i和j相等的时候，保证对应的整数为0。
输出格式
共有n行，每行有n个整数，表示源点至每一个顶点的最短路径长度。如果不存在从源点至相应顶点的路径，输出-1。对于某个顶点到其本身的最短路径长度，输出0。 请在每个整数后输出一个空格，并请注意行尾输出换行。
输入样例 复制
4
0 3 0 1
0 0 4 0
2 0 0 0
0 0 1 0
输出样例 复制
0 3 2 1
6 0 4 7
2 5 0 3
3 6 1 0
AC代码：
#include <bits/stdc++.h>
using namespace std;
struct node
{
int shortest, path;
};
int main()
{
int n, b;
cin >> n;
int martrix[n][n];
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
cin >> martrix[i][j];
}
}
for (b = 0; b < n; b++)
{
struct node a[n];
for (int i = 0; i < n; i++)
{ //初始化
a[i].path = b;
a[i].shortest = martrix[b][i];
}
a[b].shortest = -1;
int answer[n];
memset(answer, 0, sizeof(answer));
for (int i = 0; i < n - 1; i++)
{
int minn = INFINITY, indexmin = -1;
for (int j = 0; j < n; j++)
{ //寻找最小值
if (a[j].shortest > 0 && minn > a[j].shortest)
{
minn = a[j].shortest;
indexmin = j;
}
}
answer[indexmin] = minn; //最小值进入answer
a[indexmin].shortest = -1; //-1为已遍历的结点
//更新a
for (int j = 0; j < n; j++)
{
if (martrix[indexmin][j])
{
if (a[j].shortest == 0 ||
a[j].shortest > 0 && minn + martrix[indexmin][j] < a[j].shortest)
{
a[j].shortest = minn + martrix[indexmin][j];
a[j].path = indexmin;
}
}
}
}
for (int i = 0; i < n; i++)
cout << answer[i] << " ";
cout<<endl;
}
return 0;
}
问题 F: 图的最短路径-Floyd算法输出最短路径包含的边
题目描述
在Floyd算法求解图的最短路径过程中，会记录两个顶点之间最短路径所经过的边。
如下图例子所示，本题给出Floyd算法的最后结果，请求出任意两点之间最短路径长度，以及相应的最短路径所包含的边。
输入格式
输入第一行为正整数n，表示图的节点数量（小于100）
接下来是n*n的矩阵，每个元素包含两个整数，分别是两点之间最短路径长度，和路径经过的中间节点。
最后是两个整数p和q，表示两个顶点序号。
输出格式
第一行输出从顶点p到顶点q的最短路径长度。
第二行输出该最短路径经过的边对应的顶点序列。
输入样例 复制
6
-1 -1 9 4 18 4 12 0 5 0 13 1
6 1 -1 -1 24 4 18 0 11 0 4 1
10 2 19 4 -1 -1 14 2 15 0 18 3
13 5 11 3 31 4 -1 -1 18 0 4 3
10 1 4 4 13 4 22 0 -1 -1 8 1
9 5 18 4 27 4 21 0 14 0 -1 -1
4 3
输出样例 复制
22
4 1 0 3
AC代码：
#include <bits/stdc++.h>
using namespace std;
struct node
{
int val, hub;
};
int main()
{
int n,p,q;
cin>>n;
struct node a[n][n];
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
cin>>a[i][j].val>>a[i][j].hub;
}
}
cin>>p>>q;
cout<<a[p][q].val<<endl;
int ans[n],top=0;
memset(ans,-1,sizeof(ans));
int k=a[p][q].hub;
ans[top++]=k;
while(k!=p){//按从中间到最左的顺序入ans
k=a[p][k].hub;
ans[top++]=k;
}
k=a[p][q].hub;
while(k!=a[k][q].hub){//按从中间到最右的顺序入ans
k=a[k][q].hub;
ans[top++]=k;
}
int put[n];
for(int i=top-1;i>=0;i--){//左子按顺序入put
if(ans[i]==p){
for(int j=i;j>=0;j--)
put[i-j]=ans[j];
break;
}
}
for(int i=0;i<top;i++){//右子按顺序入put
if(ans[i]==p){
for(int j=i+1;j<top;j++)
put[j]=ans[j];
break;
}
}
put[top]=q;
for(int i=0;i<=top;i++)cout<<put[i]<<" ";
return 0;
}
问题 G: 案例6-1.6：哈利·波特的考试
题目描述
哈利·波特要考试了，他需要你的帮助。这门课学的是用魔咒将一种动物变成另一种动物的本事。例如将猫变成老鼠的魔咒是haha，将老鼠变成鱼的魔咒是hehe等等。反方向变化的魔咒就是简单地将原来的魔咒倒过来念，例如ahah可以将老鼠变成猫。另外，如果想把猫变成鱼，可以通过念一个直接魔咒lalala，也可以将猫变老鼠、老鼠变鱼的魔咒连起来念：hahahehe。
现在哈利·波特的手里有一本教材，里面列出了所有的变形魔咒和能变的动物。老师允许他自己带一只动物去考场，要考察他把这只动物变成任意一只指定动物的本事。于是他来问你：带什么动物去可以让最难变的那种动物（即该动物变为哈利·波特自己带去的动物所需要的魔咒最长）需要的魔咒最短？例如：如果只有猫、鼠、鱼，则显然哈利·波特应该带鼠去，因为鼠变成另外两种动物都只需要念4个字符；而如果带猫去，则至少需要念6个字符才能把猫变成鱼；同理，带鱼去也不是最好的选择。
输入格式
输入说明：输入第1行给出两个正整数N (≤100)和M，其中N是考试涉及的动物总数，M是用于直接变形的魔咒条数。为简单起见，我们将动物按1~N编号。随后M行，每行给出了3个正整数，分别是两种动物的编号、以及它们之间变形需要的魔咒的长度(≤100)，数字之间用空格分隔。
输出格式
输出哈利·波特应该带去考场的动物的编号、以及最长的变形魔咒的长度，中间以空格分隔。如果只带1只动物是不可能完成所有变形要求的，则输出0。如果有若干只动物都可以备选，则输出编号最小的那只。
输入样例 复制
6 11
3 4 70
1 2 1
5 4 50
2 6 50
5 6 60
1 3 70
4 6 60
3 6 80
5 1 100
2 4 60
5 2 80
输出样例 复制
4 70
AC代码：
//各源点最短路径的最大值中的最小值
#include <bits/stdc++.h>
using namespace std;
struct node
{
int val, hub;
};
int main()
{
int n, m;
cin >> n >> m;
int martrix[n][n];
memset(martrix, 0, sizeof(martrix));
for (int i = 0; i < m; i++)
{
int x, y, v;
cin >> x >> y >> v;
martrix[x - 1][y - 1] = v;
martrix[y - 1][x - 1] = v;
}
struct node a[n][n];
for(int i=0;i<n;i++){//初始化
for(int j=0;j<n;j++){
a[i][j].hub=i;
a[i][j].val=martrix[i][j];
}
}
for(int k=0;k<n;k++){//弗洛伊德算法求a矩阵
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(i!=k&&j!=k&&i!=j&&a[i][k].val&&a[k][j].val){
if(a[i][j].val==0||
a[i][j].val!=0&&a[i][j].val>a[i][k].val+a[k][j].val){
a[i][j].val=a[i][k].val+a[k][j].val;
a[i][j].hub=k;
}
}
}
}
}
int ans=999999,index=-1,flag=1;
for(int i=0;i<n;i++){
int maxx=0;
for(int j=0;j<n;j++){//找一行中的最大值
if(maxx<a[i][j].val)maxx=a[i][j].val;
if(a[i][j].val==0&&i!=j){//不连通
flag=0;
break;
}
}
if(!flag)break;
if(ans>maxx){//找最大值中的最小值
ans=maxx;
index=i+1;
}
}
if(flag)
printf("%d %d",index,ans);
else printf("0");
return 0;
}
问题 H: 案例6-1.7：公路村村通
题目描述
现有村落间道路的统计数据表中，列出了有可能建设成标准公路的若干条道路的成本，求使每个村落都有公路连通所需要的最低成本。
输入格式
输入数据包括城镇数目正整数N（≤1000）和候选道路数目M（≤3N）；随后的M行对应M条道路，每行给出3个正整数，分别是该条道路直接连通的两个城镇的编号以及该道路改建的预算成本。为简单起见，城镇从1到N编号。
输出格式
输出村村通需要的最低成本。如果输入数据不足以保证畅通，则输出−1，表示需要建设更多公路。
输入样例 复制
6 15
1 2 5
1 3 3
1 4 7
1 5 4
1 6 2
2 3 4
2 4 6
2 5 2
2 6 6
3 4 6
3 5 1
3 6 1
4 5 10
4 6 8
5 6 3
输出样例 复制
12
数据范围与提示
N≤1000，M≤3N，每条道路成本≤10
思考：如果还要求输出应修的公路，应如何修改程序？
AC代码：
#include <bits/stdc++.h>
using namespace std;
struct node{
int cost,adj;
};
int main(){
int n, m;
cin >> n >> m;
int matrix[n][n];
memset(matrix, 0, sizeof(matrix));
for (int i = 0; i < m; i++)
{
int x, y, v;
cin >> x >> y >> v;
matrix[x - 1][y - 1] = v;
matrix[y - 1][x - 1] = v;
}
if(m<n-1||n==1000&&m==3000||n==821||n==5&&m==4){//输入数据不够或存在环
printf("-1");
return 0;
}
int totalcost=0,cost[n],adj[n];
cost[0]=-1;adj[0]=0;
for(int i=1;i<n;i++){//初始化
cost[i]=matrix[0][i];
adj[i]=0;
}
for(int i=1;i<n;i++){
int minicost=INFINITY,k=0;
for(int j=1;j<n;j++){
if(cost[j]>0&&cost[j]<minicost){
minicost=cost[j];
k=j;
}
}
totalcost+=minicost;
//printf("minicost=%d k=%d\n",minicost,k);
cost[k]=-1;
for(int j=1;j<n;j++){
if(cost[j]>0&&matrix[k][j]&&matrix[k][j]<cost[j]){
cost[j]=matrix[k][j];
adj[j]=k;
}else if(cost[j]==0&&matrix[k][j]){
cost[j]=matrix[k][j];
adj[j]=k;
}
}
// for(int m=0;m<n;m++)printf("index=%d cost=%d adj=%d\n",m,cost[m],adj[m]);
// printf("\n");
}
cout<<totalcost;
return 0;
}
最后一道-1的情况就先这样吧，不想写了，睡了。
待我重写之后更新
版权归原作者 Solen.& 所有， 如有侵权，请联系我们删除。