做网站的职责,wordpress开发前台登录插件,城乡建设局官网,闲置电脑做网站服务器现有村落间道路的统计数据表中#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
代码实现
#includestdio.h
#includestdlib.h
typedef struct ArcNode* Arc;
struct ArcNode
{int adjvex1;int adjvex2;int weight;
};int st[1001]{0};
struct ArcNode Edge[3001];void createNode(int v1,int v2,int cost,int);
void Traverse(int);
void build(int,int);
int w0;
int flag0;
//flag用于判断是否是选择的第一条边
int main()
{int N,M;scanf(%d%d,N,M);for(int i0;iM;i){int v1,v2,cost;scanf(%d%d%d,v1,v2,cost);createNode(v1,v2,cost,i);}if(MN-1){printf(-1\n);}else{build(N,M);}return 0;
}
void createNode(int v1,int v2,int cost,int i)
{Edge[i].adjvex1v1;Edge[i].adjvex2v2;Edge[i].weightcost;return;
}
void Traverse(int M)
{//Prim算法int min1000;int pos-1;for(int i0;iM;i){int v1Edge[i].adjvex1;int v2Edge[i].adjvex2;if(flag0||(st[v1]^st[v2])){if(Edge[i].weightmin){minEdge[i].weight;posi;}}}wEdge[pos].weight;int v1Edge[pos].adjvex1;int v2Edge[pos].adjvex2;st[v1]1;st[v2]1;flag1;return;
}
void build(int N,int M)
{for(int i1;iN;i){Traverse(M);}for(int i1;iN;i){if(st[i]0){printf(-1\n);return;}}printf(%d\n,w);return;
}本题使用普利姆算法相对于克鲁斯卡尔算法更好实现
