hdu3072 Intelligence System (最小樹形圖?)

題意:給一個有向圖,問要從0號點能到達所有點所需要經過路徑的最小權值和是多少,然而,若兩點強聯通,則這兩點互相到達不需要花費。保證0號點能到達所有點

tarjan縮點以后直接取每個點入邊中花費最小的即可。

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #include<vector>
 5 #include<queue>
 6 #include<cmath>
 7 #include<ctime>
 8 #define LL long long int
 9 using namespace std;
10 const int maxn=50050,maxm=100010;
11 
12 LL rd(){
13     LL x=0;char c=getchar();int neg=1;
14     while(c<'0'||c>'9'){if(c=='-') neg=-1;c=getchar();}
15     while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
16     return x*neg;
17 }
18 
19 struct Edge{
20     int a,b,l,ne;
21 }eg[maxm];
22 int egh[maxn],ect;
23 int N,M;
24 int dfn[maxn],low[maxn],bel[maxn],stk[maxn],tot,pct,sct;
25 bool instk[maxn];
26 int mi[maxn];
27 
28 inline void adeg(int a,int b,int l){
29     eg[ect].a=a;eg[ect].b=b;eg[ect].l=l;eg[ect].ne=egh[a];egh[a]=ect++;
30 }
31 
32 void tarjan(int x){
33     dfn[x]=low[x]=++tot;
34     stk[++sct]=x;instk[x]=1;
35     for(int i=egh[x];i!=-1;i=eg[i].ne){
36         int j=eg[i].b;
37         if(instk[j]) low[x]=min(low[x],dfn[j]);
38         else if(!dfn[j]){
39             tarjan(j);low[x]=min(low[x],low[j]);
40         }
41     }
42     if(low[x]==dfn[x]){
43         ++pct;
44         while(sct){
45             instk[stk[sct]]=0;
46             bel[stk[sct]]=pct;
47             if(stk[sct--]==x) break;
48         }
49     }
50 }
51 
52 int main(){
53     int i,j,k;
54     while(~scanf("%d%d",&N,&M)){
55         memset(egh,-1,sizeof(egh));
56         memset(dfn,0,sizeof(dfn));
57         memset(instk,0,sizeof(instk));
58         ect=tot=pct=sct=0;
59         for(i=1;i<=M;i++){
60             int a=rd(),b=rd(),c=rd();
61             adeg(a,b,c);
62         }
63         
64         for(i=0;i<N;i++) if(!dfn[i]) tarjan(i);
65         memset(mi,127,sizeof(mi));
66         for(i=0;i<ect;i++){
67             if(bel[eg[i].a]==bel[eg[i].b]) continue;
68             mi[bel[eg[i].b]]=min(mi[bel[eg[i].b]],eg[i].l);
69         }int ans=0;
70         for(i=1;i<=pct;i++){
71             if(i!=bel[0]) ans+=mi[i];
72         }printf("%d\n",ans);
73     }
74 }

?

轉載于:https://www.cnblogs.com/Ressed/p/9409493.html

本文來自互聯網用戶投稿,該文觀點僅代表作者本人,不代表本站立場。本站僅提供信息存儲空間服務,不擁有所有權,不承擔相關法律責任。
如若轉載,請注明出處:http://www.pswp.cn/news/279714.shtml
繁體地址,請注明出處:http://hk.pswp.cn/news/279714.shtml
英文地址,請注明出處:http://en.pswp.cn/news/279714.shtml

如若內容造成侵權/違法違規/事實不符,請聯系多彩編程網進行投訴反饋email:809451989@qq.com,一經查實,立即刪除!

相關文章

如何在Windows 7、8、10,Vista或XP中刪除Windows服務

If you are a fan of tweaking your system and disabling services, you might find that over time your Windows Services list becomes large and unwieldy. It’s easy enough to delete a Windows service using the Command Prompt. 如果您喜歡調整系統并禁用服務&#…

縮點(有向圖的強連通分量)學習筆記

縮點(有向圖的強連通分量)學習筆記 1.什么是強連通分量&#xff1f;&#xff1a; 有向圖強連通分量:在有向圖G中&#xff0c;如果兩個頂點vi,vj間(vi>vj)有一條從vi到vj的有向路徑&#xff0c;同時還有一條從vj到vi的有向路徑&#xff0c;則稱兩個頂點強連通(strongly conne…

mysql多表聯合刪除

文件一&#xff1a;01.txt文件二&#xff1a;02.txt登錄mysql選擇數據庫表user結構表user_depart結構導入數據到表user導入數據到表user_depart聯合刪除查看刪除后user表的數據查看刪除后user_depart表的數據本文轉自 Lee_吉 51CTO博客&#xff0c;原文鏈接:http://blog.51cto.…

Jenkins 隨筆

window是 隨筆 修改端口 &#xff1a; <arguments>-Xrs -Xmx256m -Dhudson.lifecyclehudson.lifecycle.WindowsServiceLifecycle -jar "%BASE%\jenkins.war" --httpPort8181 --webroot"%BASE%\war"</arguments> 然后重啟服務&#xff08;服務…

centos 初學者_初學者:如何在Outlook 2013中創建和管理任務

centos 初學者If you’re one of those people who has a whiteboard or notepad with an ever-evolving to-do list, or your desk and monitors are adorned with Post-its reminding you of important events, then this the article for you. 如果您是擁有不斷發展的待辦事…

C語言基礎(五)

一、字符串相關函數 1.gets()(輸入字符串) 格式&#xff1a;gets(字符串)&#xff1b; (1)區別&#xff1a;gets(str)與scanf(“%s”,str) gets(str)允許輸入的字符串含有空格 scanf(“%s”,str)不允許含有空格 注意&#xff1a;由于以上無法知道字符串大小&#xff0c;很容易導…

新服務器安裝和配置zabbix的playbook

公司的金山區云服務器是由我負責的&#xff0c;每一次新購買了金山區的服務器都要把這些新服務器添加到zabbix監控里&#xff0c;于是我就編寫了一個ansible的playbook&#xff0c;這樣以后就可以在執行playbook的時候“帶薪拉屎”了。 ansible主機準備&#xff1a; 1&#xff…

15個變態的Google面試題以及答案

在當前經濟形勢不景氣的情況下&#xff0c;谷歌招聘新員工是一件令人振奮的事&#xff0c;特別是對那些在當前金融風暴中渴望找到安全港的年輕經理們和軟件開發商們來說是個好消息。   不過&#xff0c;也不要高興太早&#xff0c;谷歌在招聘新員工時&#xff0c;更加青睞名牌…

小程序禁用ios 左右滑動_如何在使用應用程序時禁用iOS控制中心

小程序禁用ios 左右滑動The Control Center has proven to be a thoughtful and welcome addition to iOS, but it can be annoying sometimes if you’re playing a game or using an app, and you accidentally open it. Here’s how you can disable it in such situations.…

repomd.xml錯誤14 not found

用Centos7最小化安裝了系統&#xff0c;想練練手&#xff0c;可以到換了“搜狐”的YUM源&#xff0c;系統總報錯更新錯誤說找不到repomd.xml。 然后就一直搜解決問題&#xff0c;能用到的都用到了&#xff0c;網上提到的都用到了。浪費了好幾個小時沒解決。正當無語的時候&…

淺談javascript遞歸(白話版)

遞歸 遞歸是一種解決問題的方法&#xff0c;通常我們可以理解成函數調用自身&#xff1b; 什么遞歸&#xff1f;遞歸怎么寫&#xff1f; 首先直接調用自身的方法和函數&#xff0c;他是一個遞歸&#xff0c;我們看代碼&#xff1a; 復制代碼 var recursiveFun function(params…

超鏈接禁用_如何在Microsoft Word中禁用超鏈接

超鏈接禁用When you type a web or email address in Word, you may notice that the program automatically formats it as a live hyperlink. This is a setting in Word’s AutoFormat feature that is on by default but can be easily turned off. 當您在Word中鍵入網站或…

ssh面試題總結

題目1&#xff1a;Hibernate工作原理及為什么要用&#xff1f; 原理&#xff1a; hibernate&#xff0c;通過對jdbc進行封裝&#xff0c;對 java類和 關系數據庫進行mapping&#xff0c;實現了對關系數據庫的面向對象方式的操作&#xff0c;改變了傳統的jdbc sql操作數據的方式…

SaltStack的salt-ssh使用及LAMP狀態設計部署

SaltStack的salt-ssh使用及LAMP狀態設計部署 1、salt-ssh的使用 官方文檔&#xff1a;https://docs.saltstack.com/en/2016.11/topics/ssh/index.html &#xff08;1&#xff09;安裝salt-ssh [rootlinux-node1 ~]# yum install -y salt-ssh&#xff08;2&#xff09;配置salt-…

程序員筆記(知識)管理的一點經驗

記筆記這件事&#xff0c;也許在很多人看來&#xff0c;再普通、簡單不過了——從小老師就教育我們要這么做。不同的人有不同的方式&#xff0c;我們最終的目的&#xff0c;還是希望不要停留在只是記錄這一層面上&#xff0c;而是將它們轉變為我們的知識。作為一個程序員&#…

xbox可以錄視頻聲音嗎_什么是Xbox Live Gold,它值得嗎?

xbox可以錄視頻聲音嗎If you have an Xbox One or Xbox 360, Microsoft’s Xbox Live Gold service is required to play multiplayer games online. A subscription costs $10 per month or $60 per year. Xbox Live Gold also includes additional benefits, like free games…

windows - mysql

Windows:(mysql)操作:0.下載安裝mysql www.mysql.org downloads community 5.7.21 下載5.6 Microsoft Windows 解壓到C: C:\mysql-5.6.39-winx64 C:\mysql-5.6.39-winx64\bin bin/mysql 客戶端 bin/mysqld 服務端 設置環境變量: …

顯示器選三星還是飛利浦_如何為飛利浦色相燈設置計時器

顯示器選三星還是飛利浦Maybe you want to turn off your Philips Hue lights after a certain amount of time has passed, or have them blink as a reminder. Whatever your needs, here’s how to set a timer for your Philips Hue lights to have them automatically tur…

PIE SDK與OpenCV結合說明文檔

1.功能簡介 OpenCV是基于BSD許可&#xff08;開源&#xff09;發行的跨平臺計算機視覺庫&#xff0c;可以運行在Linux、Windows、Android和Mac OS操作系統上。它輕量級而且高效——由一系列 C 函數和少量 C 類構成&#xff0c;同時提供了Python、Ruby、MATLAB等語言的接口&…

js的棧堆與淺拷貝、深拷貝的理解

一&#xff1a;什么是堆棧&#xff1f; 我們都知道&#xff1a;在計算機領域中&#xff0c;堆棧是兩種數據結構&#xff0c;它們只能在一端(稱為棧頂(top))對數據項進行插入和刪除。 堆&#xff1a;隊列優先,先進先出&#xff1b;由操作系統自動分配釋放 &#xff0c;存放函數的…