size stream queue truct type 个数 c89 tro
- 第1行:2个数N,M中间用空格分隔,N为点的数量,M为边的数量。(2 <= N <= 1000, 1 <= M <= 50000)
- 第2 - M + 1行:每行3个数S E W,分别表示M条边的2个顶点及权值。(1 <= S, E <= N,1 <= W <= 10000)
- 输出最小生成树的所有边的权值之和。
- 9 14
- 1 2 4
- 2 3 8
- 3 4 7
- 4 5 9
- 5 6 10
- 6 7 2
- 7 8 1
- 8 9 7
- 2 8 11
- 3 9 2
- 7 9 6
- 3 6 4
- 4 6 14
- 1 8 8
- 37
- #include < iostream > #include < cstdio > #include < map > #include < cstring > #include < string > #include < algorithm > #include < queue > #include < vector > #include < stack > #include < cstdlib > #include < cctype > #include < cstring > #include < cmath > using namespace std;
- const int inf = 0x3f3f3f3f;
- int G[1001][1001]; //邻接矩阵
- int vis[1001],
- lowc[1001];
- int prim(int G[][1001], int n) {
- int i,
- j,
- p,
- minc,
- res = 0;
- memset(vis, 0, sizeof(vis));
- vis[1] = 1; //从1开始访问
- for (i = 2; i <= n; i++) lowc[i] = G[1][i];
- for (i = 2; i <= n; i++) {
- minc = inf;
- p = -1;
- for (j = 1; j <= n; j++) {
- if (vis[j] == 0 && lowc[j] < minc) {
- minc = lowc[j];
- p = j;
- }
- }
- //cout<<minc<<endl;
- if (inf == minc) return - 1; //原图不联通
- res += minc;
- vis[p] = 1;
- for (j = 1; j <= n; j++) { //更新lowc[]
- if (vis[j] == 0 && lowc[j] > G[p][j]) {
- lowc[j] = G[p][j];
- }
- }
- }
- return res;
- }
- int main() {
- int n,
- m;
- while (cin >> n >> m) {
- int x,
- y,
- w;
- memset(G, inf, sizeof(G)); //首先记录所有边的权为inf
- for (int i = 1; i <= m; i++) {
- cin >> x >> y >> w;
- G[x][y] = G[y][x] = w;
- //cout<<G[x][y]<<endl;
- }
- //int res=prim(n);
- cout << prim(G, n) << endl;
- }
- return 0;
- }
- #include<stdio.h>
- #include<string.h>
- #include<algorithm>
- using namespace std;
- struct tr
- {
- int s,e,w;
- }p[50000+10];
- bool cmp(tr x, tr y)
- {
- return x.w < y.w;
- }
- int n,m;
- int f[1000+10];
- int i,j;
- long long ans;
- int find(int x) //找父亲
- {
- int r = x;
- while(f[r] != r)
- r = f[r];
- return r;
- int i = x, j;
- while(i != r)
- {
- j = f[i];
- f[i] = r;
- r = j;
- }
- }
- void join(int x, int y)
- {
- int fx = find(x);
- int fy = find(y);
- if(fx != fy)
- f[fx] = fy;
- }
- int kruskal()
- {
- sort(p, p+m, cmp);
- for(i=0; i<n; i++)
- {
- f[i] == i;//初始化 父亲节点
- }
- for(i=0; i<n; i++)
- {
- if(find(p[i].s) != find(p[i].e))
- {
- join(p[i].e, p[i].s);
- ans += p[i].w;
- }
- }
- return ans;
- }
- int main()
- {
- ans=0;
- scanf("%d %d",&n,&m);
- for(i=0; i<m; i++)
- {
- scanf("%d %d %d",&p[i].s, &p[i].e, &p[i].w);
- }
- kruskal();
- printf("%lld\n",ans);
- return 0;
- }
Prim算法---最小生成树
来源: http://www.bubuko.com/infodetail-2288682.html