wordpress弹框登录,seo百度推广,网站认证空间,0fees 安装 wordpress很明显聪明的同学已经发现#xff0c;这是一个稠密图#xff0c;所以用邻接矩阵。可以很好的表达#xff0c;比邻接表有优势#xff0c;所以#xff0c;采用邻接矩阵破题#xff0c; 当然也可以用邻接表#xff0c;仔细观察我的AC,会发现其实都一样#xff0c;只是存储… 很明显聪明的同学已经发现这是一个稠密图所以用邻接矩阵。可以很好的表达比邻接表有优势所以采用邻接矩阵破题 当然也可以用邻接表仔细观察我的AC,会发现其实都一样只是存储形式不一样罢了。 很明显这是一个最小生成树问题也可以认为贪心算法接下来我将分别展示两个实现路径第一个 prim 算法 第二个kruskal算法。 第一个 prim 算法哈哈原来是我最开始搞错方向了并未理解prim算法这下也是让我印象深刻了。 测试点提示内存(KB)用时(ms)结果得分0sample换数字各种回路判断1924 答案正确 15 / 151MN-1不可能有生成树1924 答案正确 2 / 22M达到N-1但是图不连通1924 答案正确 2 / 23最大N和M连通42848 答案正确 5 / 54最大N和M不连通41607 答案正确 6 / 6 第二个kruskal算法实际应用很简单果然馒头嚼碎也不见得好吸收一点点啃食的过程也是非常锻炼计算思维。 按道理来说应该是kruskal算法快但是也就一个O(N^2) 与O(NlogN),可以看出来在1000个数据点最大N(1000),M(3000)下区别还是有的。 测试点提示内存(KB)用时(ms)结果得分0sample换数字各种回路判断1884 答案正确 15 / 151MN-1不可能有生成树1884 答案正确 2 / 22M达到N-1但是图不连通1884 答案正确 2 / 23最大N和M连通41567 答案正确 5 / 54最大N和M不连通41606 答案正确 6 / 6 现有村落间道路的统计数据表中列出了有可能建设成标准公路的若干条道路的成本求使每个村落都有公路连通所需要的最低成本。 输入格式: 输入数据包括城镇数目正整数 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 算法我的AC 采用了最小堆 prim,. #includestdio.h
#includestdlib.h
#includestdbool.h#define MaxVertex 1001
#define INFITY 100001
#define MinValue -1typedef struct ENode *Edge;
struct ENode{int V1, V2;int Weight;
};typedef struct GNode *MGraph;
struct GNode{int Nv;int Ne;int G[MaxVertex][MaxVertex];
};typedef struct Sign_Dist_VNode DistNode;
struct Sign_Dist_VNode{int V;int Weight;
};typedef struct Heap *MinHeap;
struct Heap{DistNode *Data;int Size;
};MGraph Build_Graph();
MGraph Init_Graph();
void Insert_Graph(MGraph M, Edge E);
MinHeap Init_Heap(int N);
void Creat_Heap(MGraph M, MinHeap H, int Vertex, bool* Visited, bool *collected);
void Push_Heap(MinHeap H, int index, int Weight, bool *collected);
void Counterpoise_Heap(MinHeap H, int index, int V, int Weight);
bool IsEmpty_Heap(MinHeap H);
DistNode Pop_Heap(MinHeap H, bool *collected);
void Prim(MGraph M, MinHeap H, bool* Visited, int *dist);
void Print_Result(int N, int *dist, bool* Visited);int main()
{MGraph M;MinHeap H;int *dist;bool *Visited;M Build_Graph();H Init_Heap(M -Nv);dist (int*)malloc(sizeof(int) * M -Nv);Visited (bool*)calloc(M -Nv, sizeof(bool));Prim(M, H, Visited, dist);Print_Result(M -Nv, dist, Visited);return 0;
}void Prim(MGraph M, MinHeap H, bool* Visited, int *dist)
{int j;bool *collected;collected (bool*)calloc(M -Nv, sizeof(bool));for(j 1; j M -Nv; j){dist[j] M -G[0][j];}DistNode Data;Creat_Heap(M, H, 0, Visited, collected);Visited[0] true;dist[0] 0;while(Data Pop_Heap(H, collected), Data.Weight 0){Visited[Data.V] true;for(j 0; j M -Nv; j){if(!Visited[j] M -G[Data.V][j] INFITY (dist[j] M -G[Data.V][j])){dist[j] M -G[Data.V][j];Push_Heap(H, j, dist[j], collected);//有人会问这样不会产生数据重复吗注意Visited,遵循一次访问原则。}}}
}
void Print_Result(int N, int *dist, bool* Visited)
{int i, cost 0;for(i 0; i N; i){if(!Visited[i]){printf(-1\n);return ;}cost dist[i];}printf(%d\n, cost);return ;
}
MGraph Build_Graph()
{MGraph M;Edge E;M Init_Graph();E (Edge)malloc(sizeof(struct ENode));for(int i 0; i M -Ne; i){scanf(%d %d %d, E -V1, E -V2, E -Weight);E -V1 --; E -V2 --;Insert_Graph(M, E);}return M;
}
MGraph Init_Graph()
{MGraph M;M (MGraph)malloc(sizeof(struct GNode));scanf(%d %d, M -Nv, M -Ne);for(int i 0; i (M -Nv); i){for(int j 0; j (M -Nv); j){M -G[i][j] INFITY;}}return M;
}
void Insert_Graph(MGraph M, Edge E)
{M -G[E -V1][E -V2] E -Weight;M -G[E -V2][E -V1] E -Weight;
}void Creat_Heap(MGraph M, MinHeap H, int Vertex, bool* Visited, bool *collected)
{for(int j 0; j M -Nv; j){if(M -G[Vertex][j] INFITY !Visited[j]){Push_Heap(H, j, M -G[Vertex][j], collected);}}
}
MinHeap Init_Heap(int N)
{MinHeap H;H (MinHeap)malloc(sizeof(struct Heap));H -Data (DistNode*)malloc(sizeof(DistNode) * (N 1));H -Data[0].Weight MinValue;H -Size 0;return H;
}
void Push_Heap(MinHeap H, int index, int Weight, bool *collected)
{int i;if(collected[index]){for(i 1; i H -Size; i){if(index H -Data[i].V){H -Data[i].Weight Weight;Counterpoise_Heap(H, index, i, Weight);return ;}}}else{i (H -Size);Counterpoise_Heap(H, index, i, Weight);collected[index] true;return ;}
}
void Counterpoise_Heap(MinHeap H, int index, int i, int Weight)
{for(; Weight H -Data[i/2].Weight; i / 2){H -Data[i].Weight H -Data[i/2].Weight;H -Data[i].V H -Data[i/2].V;}H -Data[i].Weight Weight;H -Data[i].V index;return ;
}
bool IsEmpty_Heap(MinHeap H)
{return (H -Size 0);
}
DistNode Pop_Heap(MinHeap H, bool *collected)
{DistNode Min, Temp;int Parent, Child;if(IsEmpty_Heap(H)){return H -Data[0];}Min H -Data[1];Temp H -Data[H -Size --];collected[Min.V] false;for(Parent 1; Parent *2 H -Size; Parent Child){Child Parent * 2;if(H -Data[Child].Weight H -Data[Child 1].Weight){Child;}if(Temp.Weight H -Data[Child].Weight){break;}else{H -Data[Parent].Weight H -Data[Child].Weight;H -Data[Parent].V H -Data[Child].V;}}H -Data[Parent].Weight Temp.Weight;H -Data[Parent].V Temp.V;return Min;
} 第二个kruskal算法 最小堆并查树Kruskal。 #includestdio.h
#includestdlib.h
#includestdbool.h#define MaxVertex 1001
#define INFITY 100001
#define MinValue -1typedef struct ENode Edge;
struct ENode{int V1, V2;int Weight;
};typedef struct GNode *MGraph;
struct GNode{int Nv;int Ne;int G[MaxVertex][MaxVertex];
};typedef struct Heap *MinHeap;
struct Heap{Edge *Data;int Size;
};//便于并查树算法理解有心吧。
typedef struct UnionFind *UF;
struct UnionFind{int Parent;
};MGraph Build_Graph();
MGraph Init_Graph();
void Insert_Graph(MGraph M, Edge E);
MinHeap Init_Heap(int N);
MinHeap Creat_Heap(MGraph M);
void Push_Heap(MinHeap H, int V1, int V2, int Weight);
bool IsEmpty_Heap(MinHeap H);
Edge Pop_Heap(MinHeap H);
UF Init_UnionFind(int VertexNum);
void Union_Value(UF T, int V1, int V2);
int Find_Root(UF T, int V);
bool Check_Loop(UF T, int V1, int V2);
void Kruskal(MGraph M, MinHeap H, UF T, bool *Visited, int *dist);int main()
{MGraph M;MinHeap H;UF T;int *dist;bool *Visited;M Build_Graph();H Creat_Heap(M); T Init_UnionFind(M -Nv);dist (int*)malloc(sizeof(int) * M -Nv);Visited (bool*)calloc(M -Nv, sizeof(bool));Kruskal(M, H, T, Visited, dist);return 0;
}
void Kruskal(MGraph M, MinHeap H, UF T, bool *Visited, int *dist)
{Edge Data;int i 1;int cost 0;while(Data Pop_Heap(H), (Data.Weight 0 i M -Nv)){if(!Check_Loop(T, Data.V1, Data.V2)){Union_Value(T, Data.V1, Data.V2);cost Data.Weight;i;}}if(i ! M -Nv){printf(-1\n);}else{printf(%d\n, cost);}
}MGraph Build_Graph()
{MGraph M;Edge E;M Init_Graph();for(int i 0; i M -Ne; i){scanf(%d %d %d, E.V1, E.V2, E.Weight);E.V1 --; E.V2 --;Insert_Graph(M, E);}return M;
}
MGraph Init_Graph()
{MGraph M;M (MGraph)malloc(sizeof(struct GNode));scanf(%d %d, M -Nv, M -Ne);for(int i 0; i (M -Nv); i){for(int j 0; j (M -Nv); j){M -G[i][j] INFITY;}}return M;
}
void Insert_Graph(MGraph M, Edge E)
{M -G[E.V1][E.V2] E.Weight;M -G[E.V2][E.V1] E.Weight;
}MinHeap Creat_Heap(MGraph M)
{MinHeap H;H Init_Heap(M -Ne);for(int i 0; i M -Nv; i)for(int j i 1; j M -Nv; j){if(M -G[i][j] INFITY){Push_Heap(H, i, j, M -G[i][j]);}}return H;
}
MinHeap Init_Heap(int N)
{MinHeap H;H (MinHeap)malloc(sizeof(struct Heap));H -Data (Edge*)malloc(sizeof(Edge) * (N 1));H -Data[0].Weight MinValue;H -Size 0;return H;
}
void Push_Heap(MinHeap H, int V1, int V2, int Weight)
{int i;i (H -Size);for(; Weight H -Data[i/2].Weight; i / 2){H -Data[i].Weight H -Data[i/2].Weight;H -Data[i].V1 H -Data[i/2].V1;H -Data[i].V2 H -Data[i/2].V2;}H -Data[i].Weight Weight;H -Data[i].V1 V1;H -Data[i].V2 V2;return ;
}bool IsEmpty_Heap(MinHeap H)
{return (H -Size 0);
}
Edge Pop_Heap(MinHeap H)
{Edge Min, Temp;int Parent, Child;if(IsEmpty_Heap(H)){return H -Data[0];}Min H -Data[1];Temp H -Data[H -Size --];for(Parent 1; Parent *2 H -Size; Parent Child){Child Parent * 2;if(H -Data[Child].Weight H -Data[Child 1].Weight){Child;}if(Temp.Weight H -Data[Child].Weight){break;}else{H -Data[Parent].Weight H -Data[Child].Weight;H -Data[Parent].V1 H -Data[Child].V1;H -Data[Parent].V2 H -Data[Child].V2;}}H -Data[Parent].Weight Temp.Weight;H -Data[Parent].V1 Temp.V1;H -Data[Parent].V2 Temp.V2;return Min;
}
UF Init_UnionFind(int VertexNum)
{UF T;T (UF)malloc(sizeof(struct UnionFind) * (VertexNum 1));for(int i 0; i VertexNum; i){T[i].Parent -1;}return T;
}
void Union_Value(UF T, int V1, int V2)
{int Root1, Root2;Root1 Find_Root(T, V1);Root2 Find_Root(T, V2);if(T[Root1].Parent T[Root2].Parent){T[Root1].Parent T[Root2].Parent;T[Root2].Parent Root1;}else{T[Root2].Parent T[Root1].Parent;T[Root1].Parent Root2;}
}
int Find_Root(UF T, int V)
{if(T[V].Parent 0){return V;}return Find_Root(T, T[V].Parent);
}
bool Check_Loop(UF T, int V1, int V2)
{if(Find_Root(T, V1) Find_Root(T, V2)){return true;}else{return false;}
} 2024.9.6-错误借鉴哈哈我竟然好吧就是没有好好听课不是最短路而是最小边之前的样例我感觉只是运气吧。 测试点提示内存(KB)用时(ms)结果得分0sample换数字各种回路判断1844 答案正确 15 / 151MN-1不可能有生成树1884 答案正确 2 / 22M达到N-1但是图不连通3164 答案正确 2 / 23最大N和M连通41568 答案错误 0 / 54最大N和M不连通41567 答案正确 6 / 6
void Prim(MGraph M, MinHeap H, bool* Visited, int *dist)
{int j;bool *collected;collected (bool*)calloc(M -Nv, sizeof(bool));for(j 0; j M -Nv; j){dist[j] INFITY;}DistNode Data;Creat_Heap(M, H, 0, Visited, collected);Visited[0] true;dist[0] 0;while(Data Pop_Heap(H, collected), Data.Weight 0){if(!Visited[Data.V] dist[Data.V] Data.Weight){dist[Data.V] Data.Weight;}Visited[Data.V] true;for(j 0; j M -Nv; j){if(!Visited[j] M -G[Data.V][j] INFITY (dist[j] dist[Data.V] M -G[Data.V][j])){dist[j] M -G[Data.V][j];Push_Heap(H, j, dist[j], collected);//有人会问这样不会产生数据重复吗注意Visited,遵循一次访问原则。}}}
}
