中文亚洲精品无码_熟女乱子伦免费_人人超碰人人爱国产_亚洲熟妇女综合网

當(dāng)前位置: 首頁 > news >正文

武漢品牌網(wǎng)站建設(shè)公司哪家好在哪里可以免費自學(xué)seo課程

武漢品牌網(wǎng)站建設(shè)公司哪家好,在哪里可以免費自學(xué)seo課程,c 鮮花店網(wǎng)站建設(shè),最吉利旺財?shù)墓久謭D論——最小生成樹 A wise man changes his mind, a fool never will 生成樹 一個連通圖的生成樹是一個極小的連通子圖,它包含圖中全部的n個頂點,但只有構(gòu)成一棵樹的n-1條邊。 最小生成樹 在這些邊中選擇N-1條出來,連接所有的N個點。這N-1…

圖論——最小生成樹

A wise man changes his mind, a fool never will

生成樹

一個連通圖的生成樹是一個極小的連通子圖,它包含圖中全部的n個頂點,但只有構(gòu)成一棵樹的n-1條邊。

最小生成樹

在這些邊中選擇N-1條出來,連接所有的N個點。這N-1條邊的邊權(quán)之和是所有方案中最小的。

Prim算法(一般用于稠密圖——鄰接矩陣)

思想(貪心)

每次將離連通部分的最近的點和點對應(yīng)的邊加入的連通部分,連通部分逐漸擴(kuò)大,最后將整個圖連通起來,并且邊長之和最小。

代碼
輸入格式

第一行包含兩個整數(shù) n 和 m。

接下來 m 行,每行包含三個整數(shù) u,v,w,表示點 u 和點 v 之間存在一條權(quán)值為 w的邊。

輸出格式

共一行,若存在最小生成樹,則輸出一個整數(shù),表示最小生成樹的樹邊權(quán)重之和,如果最小生成樹不存在則輸出 impossible。

#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;const int N = 505, INF = 0x3f3f3f3f;int g[N][N], dist[N];
int n;
bool st[N];int prim() {memset(dist, 0x3f, sizeof dist);int res = 0;for (int i = 0; i < n; i ++) {int t = -1;for (int j = 1; j <= n; j ++)if (!st[j] && (t == -1 || dist[t] > dist[j]))t = j;if (i && dist[t] == INF) return INF;st[t] = true;if (i)  res += dist[t];for (int j = 1; j <= n; j ++)   dist[j] = min(dist[j], g[t][j]);}return res;
}int main() {int m;cin >> n >> m;memset(g, 0x3f, sizeof g);while (m --) {int a, b, c;cin >> a >> b >> c;g[a][b] = g[b][a] = min(g[a][b], c);}int t = prim();if (t == INF)   cout << "impossible" << endl;else    cout << t << endl;return 0;
}

Kruskal 算法(一般用于稀疏圖——鄰接表)

思想
  • 將所有邊按照權(quán)值的大小進(jìn)行升序排序,然后從小到大一一判斷。
  • 如果這個邊與之前選擇的所有邊不會組成回路(并查集),就選擇這條邊;反之,舍去。
  • 直到具有 n 個頂點的連通網(wǎng)篩選出來 n-1 條邊為止。
  • 篩選出來的邊和所有的頂點構(gòu)成此連通網(wǎng)的最小生成樹。
代碼
輸入格式

第一行包含兩個整數(shù) n 和 m。

接下來 m 行,每行包含三個整數(shù) u,v,w,表示點 u和點 v 之間存在一條權(quán)值為 w的邊。

輸出格式

共一行,若存在最小生成樹,則輸出一個整數(shù),表示最小生成樹的樹邊權(quán)重之和,如果最小生成樹不存在則輸出 impossible。

數(shù)據(jù)范圍

1 < = n < = 1 0 5 1<=n<=10^5 1<=n<=105

1 < = m < = 2 ? 1 0 5 1<=m<=2*10^5 1<=m<=2?105

圖中涉及邊的邊權(quán)的絕對值均不超過 1000。

輸入樣例:
4 5
1 2 1
1 3 2
1 4 3
2 3 2
3 4 4
輸出樣例:
6
#include <cstring>
#include <iostream>
#include <algorithm>using namespace std;const int N = 1e5 + 10, INF = 0x3f3f3f3f;struct node {int a, b, w;bool operator< (node &b)const {return w < b.w;}
}e[N * 2];int p[N];int find(int x) {if (p[x] != x)p[x] = find(p[x]);return p[x];
}int n, m;int kruskal() {sort(e, e + m);for (int i = 1; i <= n; i ++)	p[i] = i;int res = 0, cnt = 0;for (int i = 0; i < m; i ++) {int a = e[i].a, b = e[i].b, w = e[i].w;a = find(a), b = find(b);if (a != find(b)){p[a] = p[b];++ cnt;res += w;}}if (cnt < n - 1)	return INF;return res;
}int main() {cin >> n >> m;for (int i = 0; i < m; i ++) {int a, b, w;cin >> a >> b >> w;e[i] = {a, b, w};}int t = kruskal();if (t == INF)	cout << "impossible" << endl;else	cout << t << endl;return 0;
}
http://www.risenshineclean.com/news/53158.html

相關(guān)文章:

  • 山東省疫情防控最新政策seo外包收費
  • 外貿(mào)工廠 網(wǎng)站建設(shè)百度關(guān)鍵詞規(guī)劃師入口
  • 企業(yè)如何創(chuàng)建網(wǎng)站邢臺網(wǎng)站公司
  • 有沒有網(wǎng)站可以學(xué)做床上用品系統(tǒng)優(yōu)化大師下載
  • 河南seo網(wǎng)站策劃上海站優(yōu)云網(wǎng)絡(luò)科技有限公司
  • 百度官網(wǎng)認(rèn)證網(wǎng)站關(guān)鍵詞歌曲歌詞
  • asp網(wǎng)站編輯教程汕頭seo優(yōu)化項目
  • wordpress 標(biāo)簽手冊關(guān)鍵詞優(yōu)化包年推廣
  • 好看的 網(wǎng)站正在建設(shè)中源碼福州短視頻seo網(wǎng)站
  • 建站排名教育培訓(xùn)網(wǎng)站
  • 網(wǎng)頁網(wǎng)站免費佛山快速排名seo
  • 白城網(wǎng)站建設(shè)網(wǎng)站制作公司高端
  • 美武漢有什么網(wǎng)站建設(shè)公司好磁力鏈
  • 狐表做網(wǎng)站360優(yōu)化大師最新版
  • 網(wǎng)站建設(shè)的基本流程包括網(wǎng)絡(luò)營銷ppt怎么做
  • 球類網(wǎng)站如何做宣傳推廣搜索怎么選關(guān)鍵詞
  • html簡單網(wǎng)頁代碼下載廣東網(wǎng)站seo
  • 免費做公司電子畫冊的網(wǎng)站怎么優(yōu)化網(wǎng)站
  • wordpress標(biāo)簽自動生成插件下載北京谷歌seo公司
  • 什么網(wǎng)站可以做海報aso優(yōu)化報價
  • 找網(wǎng)站建設(shè)企業(yè)常德seo招聘
  • 做證券考試的網(wǎng)站電商seo是什么
  • 小說網(wǎng)站制作模板網(wǎng)絡(luò)營銷分析報告
  • 大連網(wǎng)站建設(shè)選網(wǎng)龍建網(wǎng)站
  • 做網(wǎng)站開發(fā) 用的最多的語言手機(jī)系統(tǒng)流暢神器
  • 去除wordpress主題底部信息網(wǎng)站seo綜合查詢
  • 建好的網(wǎng)站怎么用橙子建站
  • 營銷型網(wǎng)站建設(shè)的注意事項灰色行業(yè)推廣平臺
  • 如何組建網(wǎng)站開發(fā)團(tuán)隊亞馬遜alexa
  • php做的網(wǎng)站好么自己搜20條優(yōu)化措施