百度竞价排名是以什么形式来计费的广告,wordpress 国内优化,123网址之家118,免费公司取名器对于一个带权的无向连通图#xff0c;其每个生成树所有边上的权值之和可能不同#xff0c;我们把所有边上权值之和最小的生成树称为图的最小生成树。 普里姆算法是以其中某一顶点为起点#xff0c;逐步寻找各个顶点上最小权值的边来构建最小生成树。 其中运用到了回溯#…对于一个带权的无向连通图其每个生成树所有边上的权值之和可能不同我们把所有边上权值之和最小的生成树称为图的最小生成树。 普里姆算法是以其中某一顶点为起点逐步寻找各个顶点上最小权值的边来构建最小生成树。 其中运用到了回溯贪心的思想。 ----------2018年5月24日补 #begin 根据定义我们可知求一个图的最小生成树的时候一定会将所有的点都连接起来也就是说我们从任何一个点出发都可以得到这个图的最小生成树那么我这里暂定从0出发寻找到和0相连的点中最小的权值作为连接0这一个点的边如果有相同的最小权值则视要求处理将0这一个点设置为不可访问同时保存此时的连接点将求到的这一个点做和0一样相同的处理...处理出n个点就可以求得这个图的最小生成树了如果不能处理出n个点那么此图的最小生成树也就不存在。 #end 废话少说直接上题吧这些东西多练就好 一、最小生成树 题目描述 求一个连通无向图的最小生成树的代价图边权值为正整数。 输入 第 一行是一个整数N1N20表示有多少个图需要计算。以下有N个图第i图的第一行是一个整数M1M lt;50表示图的顶点数第i图的第2行至1M行为一个M*M的二维矩阵其元素ai,j表示图的i顶点和j顶点的连接情况如果 ai,j0表示i顶点和j顶点不相连如果ai,j0表示i顶点和j顶点的连接权值。 输出 每个用例用一行输出对应图的最小生成树的代价。 样例输入 1
6
0 6 1 5 0 0
6 0 5 0 3 0
1 5 0 5 6 4
5 0 5 0 0 2
0 3 6 0 0 6
0 0 4 2 6 0 样例输出 15 //Asimple
#include stdio.h
#include iostream
#include string.husing namespace std;
#define INF 0xffffff
const int maxn 55;
int G[maxn][maxn];//建图
int T, n;int prim()
{int Min, sum 0;int adv[maxn]; //保存定点下标int lowc[maxn]; //保存权值adv[0] lowc[0] 0 ;//初始化for(int i1; in; i){lowc[i] G[0][i];//先放入 第0行 的所有权值adv[i] 0 ;}//构建过程for(int i1; in; i){Min INF ;int j 1 ;int k 0 ;while( j n ){if( lowc[j]!0 lowc[j]Min){Min lowc[j] ;k j ;}j ;}sum G[adv[k]][k] ;//计算最小权值//printf(%d,%d,adv[k],k);//打印节点lowc[k] 0 ;//逐行遍历接下来的k个顶点for(int l1; ln; l){if( lowc[l]!0 G[k][l] lowc[l] ){lowc[l] G[k][l] ;adv[l] k ;}}}return sum ;
}int main()
{cin T ;while( T -- ){cin n ;for(int i0; in; i)for(int j0; jn; j){cin G[i][j];if( G[i][j] 0 i!j )G[i][j] INF ;}cout prim() endl ;}return 0;
}二、判断最小生成树是否唯一 题目描述 给出一个连通无向图请判断其最小生成树是否是唯一的。 定义1生成树给出一个连通无向图GVEG的一颗生成树被标记为TVE则具有以下性质 1VV 2T是连通无回路的。 定义2最小生成树给出一个边带权的连通无向图GVEG 的最小生成树TvE是具有最小总耗费的生成树。T的总耗费表示E 中所有边的权值的和。 输入 第 一行给出一个整数t表示测试用例数每个测试用例表示一个图测试用例的第一行给出两个整数分别表 示顶点和边的数目后面的行每行是一个三元组表示和通过权值为的边相连。任意两个节点间至多只有一条边相连。 输出 对于每个测试用例如果是唯一的输出其总耗费否则输出字符串Not Unique!. 样例输入 2
3 3
1 2 1
2 3 2
3 1 3
4 4
1 2 2
2 3 2
3 4 2
4 1 2 样例输出 3 Not Unique! #include stdio.h
#include iostream
#include string.husing namespace std;
#define INF 0xffffff
const int maxn 55;
int G[maxn][maxn];//建图
int T, n, m, x, y, num;void prim()
{int Min, sum 0;int adv[maxn]; //保存定点下标int lowc[maxn]; //保存权值bool flag false ;adv[0] lowc[0] 0 ;//初始化for(int i1; in; i){lowc[i] G[0][i];//先放入 第0行 的所有权值adv[i] 0 ;}//构建过程for(int i1; in; i){Min INF ;int j 1 ;int k 0 ;while( j n ){if( lowc[j]!0 lowc[j]Min){if( lowc[j] Min ) flag true ;Min lowc[j] ;k j ;}j ;}sum G[adv[k]][k] ;//计算最小权值lowc[k] 0 ;//逐行遍历接下来的k个顶点for(int l1; ln; l){if( lowc[l]!0 G[k][l] lowc[l] ){lowc[l] G[k][l] ;adv[l] k ;}}}if( flag ) cout Not Unique! endl ;else cout sum endl ;
}int main()
{cin T ;while( T -- ){cin n m ;for(int i0; in; i)for(int j0; jn; j){if( i j ) G[i][j] 0 ;else G[i][j] INF ;}for(int i0; im; i){cin x y num ;G[x-1][y-1] num ;G[y-1][x-1] num ;}prim();}return 0;
}2018年4月1日更正 上面的代码过不了 POJ 1679。谢谢指点~~ 今天更改了下自己的程序。 18390068Asimple1679Accepted312K16MSC1483B2018-04-01 20:08:48 //Asimple
#include iostream
#include cstdio
#include cstring
#include algorithm
#include cmath
#include queue
#include stack
using namespace std;
#define INF 0xffffff
typedef long long ll ;
const int maxn 1005;
int n, T, num, cnt, x, y, t, m, w;
int Map[maxn][maxn];void prim() {int lowc[maxn];for(int i1; in; i) lowc[i] Map[1][i];int sum 0;bool flag false;for(int l1; ln; l) {int Min INF;int k 0;for(int j2; jn; j) {if( lowc[j]!0 Min lowc[j] ) {k j;Min lowc[j];}}if( Min INF ) break; sum Min;int cnt 0;for(int i1; in; i)if( Map[k][i] lowc[k] )cnt ;if( cnt 1 ) {flag true;break;}lowc[k] 0;for(int i2; in; i) {if( lowc[i] Map[k][i] ) {lowc[i] Map[k][i];}}}if( flag ) cout Not Unique! endl;else cout sum endl;
}void input() {ios_base::sync_with_stdio(false);cin T;while( T -- ) {cin n m;for(int i1; in; i) {for(int j1; jn; j) {Map[i][j] ij?0:INF;}}while( m -- ) {cin x y w;Map[x][y] min(Map[x][y], w);Map[y][x] Map[x][y];}prim();}
}int main() {input();return 0;
} 转载于:https://www.cnblogs.com/Asimple/p/5551129.html
