word文档做网站,百度网站适配代码,网站前台模块是什么,怎样推广小程序题目#xff1a;
某省调查乡村交通状况#xff0c;得到的统计表中列出了任意两村庄间的距离。省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通#xff08;但不一定有直接的公路相连#xff0c;只要能间接通过公路可达即可#xff09;#xff0c;并要…题目
某省调查乡村交通状况得到的统计表中列出了任意两村庄间的距离。省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通但不一定有直接的公路相连只要能间接通过公路可达即可并要求铺设的公路总长度为最小。请计算最小的公路总长度。 Input 测试输入包含若干测试用例。每个测试用例的第1行给出村庄数目N ( 100 )随后的N(N-1)/2行对应村庄间的距离每行给出一对正整数分别是两个村庄的编号以及此两村庄间的距离。为简单起见村庄从1到N编号。 当N为0时输入结束该用例不被处理。 Output 对每个测试用例在1行里输出最小的公路总长度。 Sample Input 3 1 2 1 1 3 2 2 3 4 4 1 2 1 1 3 4 1 4 1 2 3 3 2 4 2 3 4 5 0 Sample Output 3 5 Huge input, scanf is recommended
分析与解答
kruskal算法 按边的权值的顺序从小到大查一遍如果不产生圈即是说uv不在一个连通分量里就把当前这条边uv之间距离加入生成树中。
先看kruskal算法把我那个sort第一次wa了就是因为我下标是从一开始的。
修修改改五分钟写了八道我算是看出点门道如果题目是以邻接矩阵形式出现就用prim算法否则用kruskal算法。 而且这种题如果加额外条件那无非就是改了一下标记数组而已。。
#includecstdio
#includealgorithm
using namespace std;
int pre[10100 ];
int find(int x) //查找根节点
{ int rx;while ( pre[r] ! r ) //返回根节点 rrpre[r];int ix , j ;while( i ! r ) //路径压缩{j pre[ i ]; //j是i的原来的父结点 pre[ i ] r ; //现在把i的父结点改成根节点 ij; //再把j的父节点改成根节点 }return r ;
}
void join(int x,int y) //判断x y是否连通//如果已经连通就不用管了 如果不连通就把它们所在的连通分支合并起,
{int fxfind(x),fyfind(y);if(fx!fy)pre[fx ]fy;
}struct node {int u,v,e;
};
bool cmp(node a,node b){return a.eb.e;
}
node edg[10010];
int m,sum;
int k(){sort(edg1,edgm1,cmp);for(int i1;im;i) pre[i]i;sum0;for(int i1;im;i){if(find(edg[i].u) ! find(edg[i].v)){join(edg[i].u,edg[i].v);sumedg[i].e;} } return sum;
}
int main()
{int t;while(scanf(%d,t)){if(t0) return 0;mt*(t-1)/2;for(int i1;im;i){scanf(%d%d%d,edg[i].u,edg[i].v,edg[i].e);}printf(%d\n,k());} }
