1231 最優佈線問題

来源:http://www.cnblogs.com/zwfymqz/archive/2017/04/16/6720130.html
-Advertisement-
Play Games

1231 最優佈線問題 1231 最優佈線問題 時間限制: 1 s 空間限制: 128000 KB 題目等級 : 白銀 Silver 時間限制: 1 s 空間限制: 128000 KB 題目等級 : 白銀 Silver 時間限制: 1 s 時間限制: 1 s 空間限制: 128000 KB 空間限制 ...


1231 最優佈線問題

 

時間限制: 1 s 空間限制: 128000 KB 題目等級 : 白銀 Silver         題目描述 Description

學校需要將n台電腦連接起來,不同的2台電腦之間的連接費用可能是不同的。為了節省費用,我們考慮採用間接數據傳輸結束,就是一臺電腦可以間接地通過其他電腦實現和另外一臺電腦連接。

為了使得任意兩台電腦之間都是連通的(不管是直接還是間接的),需要在若幹台電腦之間用網線直接連接,現在想使得總的連接費用最省,讓你編程計算這個最小的費用。

輸入描述 Input Description

輸入第一行為兩個整數n,m2<=n<=100000,2<=m<=100000),表示電腦總數,和可以互相建立連接的連接個數。接下來m行,每行三個整數a,b,c 表示在機器a和機器b之間建立連接的話費是c。(題目保證一定存在可行的連通方案, 數據中可能存在權值不一樣的重邊,但是保證沒有自環)

輸出描述 Output Description

輸出只有一行一個整數,表示最省的總連接費用。

樣例輸入 Sample Input

3 3

1 2 1

1 3 2

2 3 1

樣例輸出 Sample Output

2

數據範圍及提示 Data Size & Hint

最終答案需要用long long類型來保存

 

水題 裸卡路絲卡爾

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 const int MAXN=300001;
 7 struct node
 8 {
 9     int u;
10     int v;
11     int w;
12 }edge[MAXN];
13 int num=1;
14 int father[MAXN];
15 int comp(const node & a,const node & b)
16 {
17     if(a.w<b.w)return 1;
18     else return 0;
19 }
20 int find(int x)
21 {
22     if(father[x]!=x)
23     father[x]=find(father[x]);
24     return father[x];
25 }
26 void unionn(int x,int y)
27 {
28     int fx=find(x);
29     int fy=find(y);
30     father[fx]=fy;
31 }
32 int main()
33 {
34     int n,m;
35     scanf("%d%d",&n,&m);
36     for(int i=1;i<=n;i++)father[i]=i;
37     for(int i=1;i<=m;i++)
38     {
39         scanf("%d%d%d",&edge[num].u,&edge[num].v,&edge[num].w);
40         num++;
41     }
42     sort(edge+1,edge+num,comp);
43     long long int k=0;
44     long long int tot=0;
45     for(int i=1;i<=num-1;i++)
46     {
47         if(find(edge[i].u)!=find(edge[i].v))
48         {
49             unionn(edge[i].u,edge[i].v);
50             tot=tot+edge[i].w;
51             k++;
52         }
53         if(k==n-1)break;
54     }
55     printf("%lld",tot);
56     return 0;
57 }

 


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • 背景 去年年底接到的新需求,需要將原來用Swing做的桌面應用中的一個功能做成Web版的,並且要集成到原應用中,換言之就是要使用內嵌瀏覽器。最開始考慮的是JavaFx提供的WebView,優點是不需要其他第三方庫,jdk1.7開始集成。但是開發完成之後發現兩個比較嚴重的問題,一是界面有一個比較複雜的 ...
  • 後續要做個日誌相關的東西,先筆記一下。 slf4j是日誌框架的一個門面端,背後實現者有log4j,logback等等。 如何實現這個門面的呢? 一般我們使用的代碼如下: slf4j 的LoggerFactory具體實現了門面模式中對接各種實現的事情。 getILoggerFactory方法: 上面, ...
  • 1、在創建之初,可以選擇自己想要使用的python版本。 如果之後想要更換Python版本,可以通過~~~更換選擇Python版本。 2、創建.py文件,點擊文件名,出現如下界面: 點擊new--python_file,就可以成功創建.py文件。 3、因為我的這一版pycharm死活找不到file- ...
  • 工廠模式(Factory pattern)和單例模式一樣,是另外一種創建型模式。和單例模式不同的是,單例模式會創建和管理一個單獨的類型的單一對象,工廠模式則是用於創建多種不同類型的類的多個對象。 ...
  • Java容器指的是List,Set,Map這些類。由於翻譯的問題,問到集合,Collection這些指的都是它們幾個。 List ArrayList 隨機訪問快 LinkedList 插入刪除快 這個好理解,array嘛就是數組,隨機訪問快。link嘛就是鏈表,當然是插入刪除快了。 Set 每個元素 ...
  • 最近在學習JavaWeb, 但是在第一步的時候就出現問題了, 什麼問題呢, 就是關於Tomact的配置。 下麵我就詳細說明一下我配置過程中出現的問題以及怎麼解決的, 希望對大家能有所幫助。 首先,我們可以進入你安裝Tomact的bin目錄下, 然後你就可以發現有個文件, 名稱為startup.bat ...
  • datetime模塊用於是date和time模塊的合集,datetime有兩個常量,MAXYEAR和MINYEAR,分別是9999和1. datetime模塊定義了5個類,分別是 1.datetime.date:表示日期的類 2.datetime.datetime:表示日期時間的類 3.dateti ...
  • 前段時間使用c++做項目開發,需要根據根據配置文件路徑載入全局配置文件,並對外提供唯一訪問點。面對這樣一個需求,自然的就想到了使用單例模式來創建一個單例配置對象,供外部調用。一開始想使用boost中自帶的單例類來實現,但是遺憾的是,boost中的的單例類好像只能使用無參的類構造函數,而我希望將配置文 ...
一周排行
    -Advertisement-
    Play Games
  • 移動開發(一):使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說,近來想嘗試開發一款安卓APP,考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP,畢竟是使用Visual Studio開發工具,使用起來也比較的順手,結合微軟官方的教程進行了安卓 ...
  • 前言 QuestPDF 是一個開源 .NET 庫,用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫,它徹底改變了我們生成 PDF 文檔的方 ...
  • 項目地址 項目後端地址: https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址: ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址: http://tree ...
  • 話不多說,直接開乾 一.下載 1.官方鏈接下載: https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe,運行開始下載SQL server; 二. ...
  • 前言 隨著物聯網(IoT)技術的迅猛發展,MQTT(消息隊列遙測傳輸)協議憑藉其輕量級和高效性,已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫,為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog支持多種接收器用於日誌存儲,增強器用於添加屬性,LogContext管理動態屬性,支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項,適用於不同需求。 ...
  • 目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據,爬取信息時需要模擬瀏覽器行為,否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下: 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • 1.前言 什麼是熱更新 游戲或者軟體更新時,無需重新下載客戶端進行安裝,而是在應用程式啟動的情況下,在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR,Xlua,ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles,Addressable, ...
  • 本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺,其實像阿裡雲,騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後,它會送 ...
  • 通過以下方式可以高效,並保證數據同步的可靠性 1.API設計 使用RESTful設計,確保API端點明確,並使用適當的HTTP方法(如POST用於創建,PUT用於更新)。 設計清晰的請求和響應模型,以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證,確保接收到的數據符合預期格 ...