怎么做才能提高网站权重,深圳做网站要,万家灯火营销型网站,蓬莱专业做网站公司题目
现有村落间道路的统计数据表中#xff0c;列出了有可能建设成标准公路的若干条道路的成本#xff0c;求使每个村落都有公路连通所需要的最低成本。
输入格式: 输入数据包括城镇数目正整数N#xff08;≤1000#xff09;和候选道路数目M#xff08;≤3N#xff09;…题目
现有村落间道路的统计数据表中列出了有可能建设成标准公路的若干条道路的成本求使每个村落都有公路连通所需要的最低成本。
输入格式: 输入数据包括城镇数目正整数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
分析 一个典型的最小生成树问题可以用Prim或Kruskal实现本文使用Prim用循环和最小堆2种方式实现。
循环代码
#include stdio.h
#include stdlib.h#define MAX_VERTEX_NUM 1000
#define INFINITY 65535
#define ERROR -1typedef int Vertex;
typedef int WeightType;struct _Edge
{Vertex V, W;WeightType weight;
};
typedef struct _Edge *Edge;typedef struct _AdjNode *AdjNode;
struct _AdjNode
{Vertex adjV;WeightType weight;AdjNode next;
};typedef struct AdjTable
{AdjNode firstEdge;
} AdjTable[MAX_VERTEX_NUM];struct _LGraph
{int Nv, Ne;AdjTable graph;
};
typedef struct _LGraph *LGraph;LGraph CreateGraph(int vertexNum);
void InsertEdge(LGraph graph, Edge E);
LGraph BuildGraph(int vertexNum, int edgeNum);
Vertex FindMinDist(LGraph G, WeightType dist[]);
int Prim(LGraph graph, Vertex S);/*
08-图7 公路村村通
难度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 3126 4
1 2 5
1 3 3
1 4 7
5 6 26 6
1 2 10
2 4 20
3 4 30
1 3 40
1 4 50
2 3 604 4
1 2 10
2 3 20
3 4 30
1 4 404 6
1 2 10
1 3 40
1 4 50
2 3 60
2 4 20
3 4 30
602 1
1 2 107 21
1 2 14
1 3 11
1 4 19
1 5 12
1 6 17
1 7 20
2 3 16
2 4 15
2 5 13
2 6 10
2 7 18
3 4 20
3 5 12
3 6 11
3 7 16
4 5 14
4 6 17
4 7 19
5 6 10
5 7 15
6 7 137 21
1 2 14
1 3 11
1 4 19
1 5 12
1 6 17
1 7 20
2 3 16
2 4 15
2 5 13
2 6 10
2 7 18
3 4 20
3 5 12
3 6 11
3 7 16
4 5 14
4 6 17
4 7 19
5 6 10
5 7 15
6 7 13*/int main()
{int N, M;scanf(%d %d, N, M);LGraph G BuildGraph(N, M);printf(%d\n, Prim(G, 0));free(G);return 0;
}LGraph CreateGraph(int vertexNum)
{LGraph G;G (LGraph)malloc(sizeof(struct _LGraph));G-Nv vertexNum;G-Ne 0;for (int V 0; V G-Nv; V){G-graph[V].firstEdge NULL;}return G;
}void InsertEdge(LGraph G, Edge E)
{AdjNode NewNode;NewNode (AdjNode)malloc(sizeof(struct _AdjNode));NewNode-adjV E-W;NewNode-weight E-weight;NewNode-next G-graph[E-V].firstEdge;G-graph[E-V].firstEdge NewNode;NewNode (AdjNode)malloc(sizeof(struct _AdjNode));NewNode-adjV E-V;NewNode-weight E-weight;NewNode-next G-graph[E-W].firstEdge;G-graph[E-W].firstEdge NewNode;
}LGraph BuildGraph(int vertexNum, int edgeNum)
{LGraph G CreateGraph(vertexNum);G-Ne edgeNum;Edge E;E (Edge)malloc(sizeof(struct _Edge));for (int i 0; i G-Ne; i){scanf(%d %d %d, E-V, E-W, E-weight);E-V--;E-W--;InsertEdge(G, E);}free(E);return G;
}Vertex FindMinDist(LGraph G, WeightType dist[])
{ /* 返回未被收录顶点中dist最小者 */Vertex minV, V;WeightType minDist INFINITY;for (V 0; V G-Nv; V){if (dist[V] ! 0 dist[V] minDist){/* 若V未被收录且dist[V]更小 */minDist dist[V]; /* 更新最小距离 */minV V; /* 更新对应顶点 */}}if (minDist INFINITY) /* 若找到最小dist */return minV; /* 返回对应的顶点下标 */elsereturn ERROR; /* 若这样的顶点不存在返回-1作为标记 */
}int Prim(LGraph G, Vertex S)
{ // 只计算TotalWeight无需实际创建生成树WeightType dist[G-Nv], totalWeight;Vertex V;AdjNode W;int vCount;for (V 0; V G-Nv; V)dist[V] INFINITY;for (W G-graph[S].firstEdge; W; W W-next)dist[W-adjV] W-weight;totalWeight 0;vCount 0;dist[S] 0;vCount;while (1){V FindMinDist(G, dist);if (V ERROR)break;totalWeight dist[V];dist[V] 0;vCount;for (W G-graph[V].firstEdge; W; W W-next){if (dist[W-adjV] ! 0){if (W-weight dist[W-adjV]){dist[W-adjV] W-weight;}}}}if (vCount G-Nv) /* MST中收的顶点少于|V|-1个 */totalWeight ERROR;return totalWeight;
}最小堆代码
#include stdio.h
#include stdlib.h
#include stdbool.h#define MIN_DATA -1000
#define ELEMENT_TYPE int
#define MAX_VERTEX_NUM 1000
#define INFINITY 65535
#define ERROR -1typedef int Vertex;
typedef int WeightType;struct _MinHeap
{ELEMENT_TYPE *Elements;int Size;int Capacity;
};
typedef struct _MinHeap *MinHeap;struct _Edge
{Vertex V, W;WeightType weight;
};
typedef struct _Edge *Edge;typedef struct _AdjNode *AdjNode;
struct _AdjNode
{Vertex adjV;WeightType weight;AdjNode next;
};typedef struct AdjTable
{AdjNode firstEdge;
} AdjTable[MAX_VERTEX_NUM];struct _LGraph
{int Nv, Ne;AdjTable graph;
};
typedef struct _LGraph *LGraph;MinHeap CreateHeap(int MaxSize);
bool isEmpty(MinHeap H);
bool isFull(MinHeap H);
ELEMENT_TYPE DelMin(MinHeap H, int dist[]);
void BuildMinHeap(MinHeap H, int dist[]);
void PercUp(MinHeap H, int p, int dist[]);LGraph CreateGraph(int vertexNum);
void InsertEdge(LGraph graph, Edge E);
LGraph BuildGraph(int vertexNum, int edgeNum);void UpdateHeap(MinHeap H, int dist[], Vertex V);
Vertex FindMinDist(MinHeap H, int dist[]);
int Prim(LGraph graph, Vertex S);/*
08-图7 公路村村通
难度2星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 3126 4
1 2 5
1 3 3
1 4 7
5 6 24 4
1 2 10
2 3 20
3 4 30
1 4 404 6
1 2 10
1 3 40
1 4 50
2 3 60
2 4 20
3 4 30607 21
1 2 14
1 3 11
1 4 19
1 5 12
1 6 17
1 7 20
2 3 16
2 4 15
2 5 13
2 6 10
2 7 18
3 4 20
3 5 12
3 6 11
3 7 16
4 5 14
4 6 17
4 7 19
5 6 10
5 7 15
6 7 13*/int main()
{int N, M;scanf(%d %d, N, M);LGraph G BuildGraph(N, M);printf(%d\n, Prim(G, 0));free(G);return 0;
}LGraph CreateGraph(int vertexNum)
{LGraph G;G (LGraph)malloc(sizeof(struct _LGraph));G-Nv vertexNum;G-Ne 0;for (int V 0; V G-Nv; V){G-graph[V].firstEdge NULL;}return G;
}void InsertEdge(LGraph G, Edge E)
{AdjNode newNode;newNode (AdjNode)malloc(sizeof(struct _AdjNode));newNode-adjV E-W;newNode-weight E-weight;newNode-next G-graph[E-V].firstEdge;G-graph[E-V].firstEdge newNode;newNode (AdjNode)malloc(sizeof(struct _AdjNode));newNode-adjV E-V;newNode-weight E-weight;newNode-next G-graph[E-W].firstEdge;G-graph[E-W].firstEdge newNode;
}LGraph BuildGraph(int vertexNum, int edgeNum)
{LGraph G CreateGraph(vertexNum);G-Ne edgeNum;Edge E;E (Edge)malloc(sizeof(struct _Edge));for (int i 0; i G-Ne; i){ // 用E-V--E-W--解决顶点序号从1开始的问题scanf(%d %d %d, E-V, E-W, E-weight);E-V--;E-W--;InsertEdge(G, E);}free(E);return G;
}Vertex FindMinDist(MinHeap H, int dist[])
{Vertex minV ERROR;// 从堆中取出最小值并维护最小堆的有效性。minV DelMin(H, dist);return minV;
}int Prim(LGraph G, Vertex S)
{ // 只计算TotalWeight无需实际创建生成树WeightType dist[G-Nv], totalWeight;Vertex V;AdjNode W;int vCount;for (V 0; V G-Nv; V)dist[V] INFINITY;for (W G-graph[S].firstEdge; W; W W-next)dist[W-adjV] W-weight;totalWeight 0;vCount 0;dist[S] 0;vCount;// 根据dist对未收录顶点创建最小堆MinHeap H CreateHeap(G-Nv);for (V 0; V G-Nv; V){if (dist[V] ! 0){ // H-Elements保存的是未收集顶点的编号本例依次是1,2,3H-Elements[H-Size] V;}}BuildMinHeap(H, dist);while (1){V FindMinDist(H, dist);if (V ERROR)break;totalWeight dist[V];dist[V] 0;vCount;for (W G-graph[V].firstEdge; W; W W-next){if (dist[W-adjV] ! 0){if (W-weight dist[W-adjV]){ /*目标是调整H-Elements,改了吗没有也没有必要H-Elements保存的是顶点。现在要做的是定位到W-adjV对应顶点做percup*/dist[W-adjV] W-weight;UpdateHeap(H, dist, W-adjV);}}}}if (vCount G-Nv) /* MST中收的顶点少于|V|-1个 */totalWeight ERROR;return totalWeight;
}MinHeap CreateHeap(int MaxSize)
{MinHeap H (MinHeap)malloc(sizeof(struct _MinHeap));H-Elements (ELEMENT_TYPE *)malloc((MaxSize 1) * sizeof(ELEMENT_TYPE));H-Elements[0] MIN_DATA;H-Size 0;H-Capacity MaxSize;return H;
}bool isEmpty(MinHeap H)
{return H-Size 0;
}bool isFull(MinHeap H)
{return H-Size H-Capacity;
}ELEMENT_TYPE DelMin(MinHeap H, int dist[])
{if (!isEmpty(H)){ELEMENT_TYPE min, last;int parent, child;min H-Elements[1];last H-Elements[H-Size--];for (parent 1; 2 * parent H-Size; parent child){child 2 * parent;if ((child ! H-Size) (dist[H-Elements[child]] dist[H-Elements[child 1]])){child;}if (dist[last] dist[H-Elements[child]]){break;}else{H-Elements[parent] H-Elements[child];}}H-Elements[parent] last;if (dist[min] INFINITY)return min;elsereturn ERROR;}else{return ERROR;}
}void PercUp(MinHeap H, int p, int dist[])
{ /*根据顶点的dist值决定顶点在堆中的存储位置。对dist[H-Elements[child]] dist[H-Elements[child 1]]的理解dist[x] dist[y],本质是比较两个顶点之间的dist值x,y是顶点序号。dist[x]的初始值通过dist[V] G-dist[S][V]获得并用dist[W] dist[V] G-dist[V][W]更新child是顶点在堆中的索引H-Elements[child]存储的是顶点序号所以dist[H-Elements[child]]是顶点的dist值。*/int parent, child;ELEMENT_TYPE X;X H-Elements[p];for (parent p; 2 * parent H-Size; parent child){child 2 * parent;if ((child ! H-Size) (dist[H-Elements[child]] dist[H-Elements[child 1]])){child;}if (dist[X] dist[H-Elements[child]]){break;}else{H-Elements[parent] H-Elements[child];}}H-Elements[parent] X;
}void BuildMinHeap(MinHeap H, int dist[])
{ // p表示顶点在堆中的位置int p;for (p H-Size / 2; p 0; p--){PercUp(H, p, dist);}
}void UpdateHeap(MinHeap H, int dist[], Vertex V)
{int i, idx, x;// 找到V在堆中的位置for (i 1; i H-Size; i){if (H-Elements[i] V){idx i;x dist[H-Elements[idx]];break;}}// 更新V的dist值并向上调整堆// dist[V] dist[H-Elements[i]];/* 是否需要条件i1*/for (i idx; i 1 dist[H-Elements[i / 2]] x; i / 2){H-Elements[i] H-Elements[i / 2];}H-Elements[i] V;
}
小结: 典型的Prim应用姥姥没有讲最小堆的具体实现代码磨了很久终于过了。简言之只有对最小生成树算法逻辑有深刻的认识同时有足够的耐心和细心实际动手写才能提高代码能力。
结果
