淘客网站建设教程,easyphp wordpress,网站建设用到什么,创建一个自己的网站的步骤一#xff1a;题目
某地区经过对城镇交通状况的调查#xff0c;得到现有城镇间快速道路的统计数据#xff0c;并提出“畅通工程”的目标#xff1a;使整个地区任何两个城镇间都可以实现快速交通#xff08;但不一定有直接的快速道路相连#xff0c;只要互相间接通过快速…一题目
某地区经过对城镇交通状况的调查得到现有城镇间快速道路的统计数据并提出“畅通工程”的目标使整个地区任何两个城镇间都可以实现快速交通但不一定有直接的快速道路相连只要互相间接通过快速路可达即可。现得到城镇道路统计表表中列出了任意两城镇间修建快速路的费用以及该道路是否已经修通的状态。现请你编写程序计算出全地区畅通需要的最低成本。
输入格式: 输入的第一行给出村庄数目N (1≤N≤100)随后的N(N−1)/2行对应村庄间道路的成本及修建状态每行给出4个正整数分别是两个村庄的编号从1编号到N此两村庄间道路的成本以及修建状态 — 1表示已建0表示未建。
输出格式: 输出全省畅通需要的最低成本。
输入样例:
4
1 2 1 1
1 3 4 0
1 4 1 1
2 3 3 0
2 4 2 1
3 4 5 0输出样例:
3二思路
这个就是Prime算法的变型我想的是如果这条路是已经修过那么的话就将其的权值你设为0
三:上码
/**思路如果是已经修过那么的话就将其的权值你设为0*/
#includebits/stdc.h
using namespace std;typedef struct GNode* PtrGraph;typedef struct GNode{int Nv;int Ne;int Data[105][105];
}gnode;int N;
//利用邻接矩阵储存图的基本信息
void CreateGraph(PtrGraph G){cin N;G-Nv N;G-Ne N*(N-1)/2;//矩阵初始化 for(int i 1; i G-Nv; i){for(int j 1; j G-Nv; j){G-Data[i][j] 0; }}//矩阵赋值for(int i 0; i G-Ne; i){int a,b,c,d;cin a b c d; if(d 0){G-Data[a][b] c;G-Data[b][a] c; } }
}
//输出矩阵
void print_Graph(PtrGraph G){for(int i 1; i G-Nv; i){for(int j 1; j G-Nv; j){cout G-Data[i][j] ;}cout endl;}
} //Prime最小成树的算法
void Prime(PtrGraph G){int dist[105];int visited[105] {0};int count 0;for(int i 1; i G-Nv; i){dist[i] G-Data[1][i];//将符号为1到其他点的距离存在 dist数组中 }visited[1] 0;count;while(1){int m -1;int infinite 9999;//求取最小值for(int i 1; i G-Nv; i){if(dist[i] infinite visited[i] ! 1){infinite dist[i];m i;}}visited[m] 1;count;if(m -1){break;} //更新for(int i 1; i G-Nv; i){if(visited[i] ! 1 G-Data[m][i] dist[i] ){dist[i] G-Data[m][i];}} } int sum 0;for(int i 1; i G-Nv; i){sum dist[i];}cout sum;} int main(){PtrGraph G (PtrGraph)malloc(sizeof(struct GNode));CreateGraph(G);
// print_Graph(G);Prime(G);}加油BOY
