PTA数据结构与算法题目集(中文) 7-10
2024-08-28 14:59:22
PTA数据结构与算法题目集(中文) 7-10
7-10 公路村村通 (30 分)
现有村落间道路的统计数据表中,列出了有可能建设成标准公路的若干条道路的成本,求使每个村落都有公路连通所需要的最低成本。
输入格式:
输入数据包括城镇数目正整数N(≤)和候选道路数目M(≤);随后的M行对应M条道路,每行给出3个正整数,分别是该条道路直接连通的两个城镇的编号以及该道路改建的预算成本。为简单起见,城镇从1到N编号。
输出格式:
输出村村通需要的最低成本。如果输入数据不足以保证畅通,则输出−,表示需要建设更多公路。
输入样例:
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
题目分析:一道图的最小生成树算法的基础题 利用Prim或Kruskal算法来解决最小生成树问题 稠密图用Prim算法 稀疏图使用Kruskal算法 注意收录顶点在找到后就立刻进行 这样就不会对对角线上的元素进行判断
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#define MAXVERTEXNUM 1000
#define INIFITY 65535 typedef struct ENode* Edge;
struct ENode
{
int V1, V2;
int Weight;
}; typedef struct GNode* Graph;
struct GNode
{
int Nv;
int Ne;
int G[MAXVERTEXNUM][MAXVERTEXNUM];
}; Graph BuildGraph(int VertexNum)
{
Graph Gra = (Graph)malloc(sizeof(struct GNode));
Gra->Nv = VertexNum;
Gra->Ne = ;
for(int i=;i<=Gra->Nv;i++)
for (int j = ; j <=Gra->Nv; j++)
{
if (i == j)
Gra->G[i][j] = ;
else
Gra->G[i][j] = INIFITY;
}
return Gra;
} void Insert(Edge E, Graph Gra)
{
Gra->G[E->V1][E->V2] = E->Weight;
Gra->G[E->V2][E->V1] = E->Weight;
} Graph CreateGraph()
{
int N, M;
scanf("%d%d", &N, &M);
Edge E = (Edge)malloc(sizeof(struct GNode));
Graph Gra = BuildGraph(N);
Gra->Ne = M;
for (int i = ; i < M; i++)
{
scanf("%d%d%d", &(E->V1), &(E->V2), &(E->Weight));
Insert(E, Gra);
}
return Gra;
} int IsEdge(Graph Gra, int V, int W)
{
return Gra->G[V][W] < INIFITY;
} int Dist[MAXVERTEXNUM];
int Path[MAXVERTEXNUM];
int Collected[MAXVERTEXNUM];
int Sum;
int FindMin(Graph Gra)
{
int MinDist = INIFITY;
int Min = -;
for (int i = ; i <=Gra->Nv; i++)
if (!Collected[i] && Dist[i] < MinDist)
{
MinDist = Dist[i];
Min = i;
}
return Min;
}
void Prim(Graph Gra,int V)
{
Dist[V] = ;
Path[V] = -;
Collected[V] = ;
for (int i = ; i <= Gra->Nv; i++)
{
Dist[i] = Gra->G[V][i];
Path[i] = V;
}
while ()
{
int Min = FindMin(Gra);
if (Min ==-)
break;
Collected[Min] = ;
Dist[Min] = ;
Sum += Gra->G[Path[Min]][Min];
for (int i = ; i <=Gra->Nv; i++)
{
if (!Collected[i] && IsEdge(Gra, Min, i))
if (Gra->G[Min][i] < Dist[i])
{
Dist[i] = Gra->G[Min][i];
Path[i] = Min;
}
}
}
} int main()
{
Graph Gra = CreateGraph();
Prim(Gra,);
int Flag =;
for (int i = ; i <= Gra->Nv; i++)
if (!Collected[i])
Flag = ;
if (Flag)
printf("%d", Sum);
else
printf("-1");
return ;
}
最新文章
- C代码工具--自动生成enum值和名字映射代码
- js 原生 ajax 异步上传图片
- 【转】【WPF】 WPF 调用API修改窗体风格实现真正的无边框窗体
- POJ1163 The Triangle: 倒三角形问题
- HDU-1339 A Simple Task
- Android 给Button加个监听
- MVC-07 案例2
- linux 高精度定时器例子
- iOS开发之WKWebView代替UIWebView
- vscode插件安装失败的解决方案
- java 写 Excel(不生成实体文件,写为流的形式)
- 剑指offer——python【第3题】从尾到头打印链表
- json扩展
- mysql 开启远程访问
- 面试:http协议
- windows server 2016 无法联网问题
- VMware两台虚拟机之间文件共享
- TCP建立连接和断开连接过程
- 转 Android Activity之间动画完整版详解
- spring事务的一些注意点