【Tarjan】+【SPFA】【APIO2009】Atm

来源:http://www.cnblogs.com/Maki-Nishikino/archive/2016/09/13/5868953.html
-Advertisement-
Play Games

一、演算法介紹 tarjan——求解有向圖強連通分量。這個演算法在本人的一篇blog中有介紹,這裡就不贅述了。貼上介紹tarjan的的blog鏈接:http://www.cnblogs.com/Maki-Nishikino/p/5866191.html 那麼接下來說說SPFA: SPFA全稱Shorte ...


一、演算法介紹

tarjan——求解有向圖強連通分量。這個演算法在本人的一篇blog中有介紹,這裡就不贅述了。貼上介紹tarjan的的blog鏈接:http://www.cnblogs.com/Maki-Nishikino/p/5866191.html

那麼接下來說說SPFA:

SPFA全稱Shortest Path Faster Algorithm,用於求解單源最短路。既然名字中有“Faster”,那它就一定有過人之處,事實上它也的確比Dijkstra和Bellman-Ford更高效。

它的思路大致如下:
1、先用鄰接表把圖存下來,並且規定一個數組d,d[i]表示起點到i的最短路程;

2、建立一個隊列,將起點放入隊列;

3、對隊首元素執行鬆弛操作,遍歷所有以隊首元素為起點的邊,如果被遍歷的邊可以使到被遍歷的邊的終點的路徑變短,那麼就更新這個最短路徑,並把被遍歷的邊的終點放到隊尾;

4、每完成一次鬆弛,就令隊首元素出隊,重覆2,直到隊列里沒有元素。

原諒博主懶得貼偽代碼,我就直接講題了,反正題解里也有模板#手動滑稽

二、APIO2009 Atm題解

原題鏈接(來自bzoj):http://www.lydsy.com/JudgeOnline/problem.php?id=1179

題目描述:

輸入:

  第一行包含兩個整數N、M。N表示路口的個數,M表示道路條數。接下來M行,每行兩個整數,這兩個整數都在1到N之間,第i+1行的兩個整數表示第i條道路的起點和終點的路口

編號。接下來N行,每行一個整數,按順序表示每個路口處的ATM機中的錢數。接下來一行包含兩個整數S、P,S表示市中心的編號,也就是出發的路口。P表示酒吧數目。接下來

的一行中有P個整數,表示P個有酒吧的路口的編號。

輸出:

輸出一個整數,表示Banditji從市中心開始到某個酒吧結束所能搶劫的最多的現金總數。

樣例輸入:

6 7

1 2

2 3

3 5

2 4

4 1

2 6

6 5

10

12

8

16

1

5

1 4
4

3

5

6

樣例輸出:

47

數據範圍:

  50%的輸入保證N, M<=3000。所有的輸入保證N, M<=500000。每個ATM機中可取的錢數為一個非負整數且不超過4000。輸入數據保證你可以從市中心沿著Siruseri的單向的道路到達其中的至少一個酒吧。


對於這道題,我們考慮先用tarjan求出它的所有強連通分量,再把同一個強連通分量上的ATM機的錢加起來,讓一個強連通分量上的點縮成一個點。然後以市中心s為起點,用SPFA跑出s到其他點的最長(最有價值)路,比較酒吧所在點的d值,輸出大的即可。

附上代碼:

 

  1 #include<stdio.h>
  2 #include<algorithm>
  3 #include<string.h>
  4 using namespace std;
  5 struct node
  6 {
  7     int v;
  8     int next;
  9 };
 10 int n,m;
 11 node e[500010],map[500010];//鄰接表存圖 
 12 int st[500010],head[500010],cnt;
 13 int atm[500010],money[500010];
 14 int d[500010],q[500010];//最短路徑&SPFA要用的隊列 
 15 void build(int a,int b)
 16 {
 17     e[++cnt].v=b;
 18     e[cnt].next=st[a];
 19     st[a]=cnt;
 20 }//建圖找強連通分量 
 21 int stack[500010],top;//tarjan需要的棧 
 22 int dfn[500010],low[500010],dex;//時間戳(深搜序)、可回溯到的最早棧中時間戳、次序編號 
 23 bool vis[500010];//tarjan時判斷點是否在棧中,SPFA時判斷點是否在隊列中 
 24 int color[500010],num;//表示同一強連通分量上的點 
 25 void tarjan(int x)//tarjan找強連通分量 
 26 {
 27     dfn[x]=++dex;
 28     low[x]=dex;
 29     vis[x]=true;
 30     stack[++top]=x;//當前點入棧
 31     int i;
 32     for(i=st[x];i!=0;i=e[i].next)//枚舉以當前點為起點的邊 
 33     {
 34         int temp=e[i].v;//temp為當前被枚舉邊的終點 
 35         if(!dfn[temp])//如果當前邊終點未被處理 
 36         {
 37             tarjan(temp);
 38             low[x]=min(low[x],low[temp]);
 39         }
 40         else if(vis[temp])low[x]=min(low[x],dfn[temp]);
 41     }
 42     if(dfn[x]==low[x])
 43     {
 44         vis[x]=false;
 45         color[x]=++num;//標記當前強連通分量內的點  
 46         while(stack[top]!=x)//棧頂元素依次出棧 
 47         {
 48             color[stack[top]]=num;
 49             vis[stack[top--]]=false;
 50         }
 51         top--;
 52     }
 53 }
 54 void add()// 把同一強連通分量上的點縮成一個點,把這些點連成一張新圖 
 55 {
 56     cnt=0;
 57     int i,j;
 58     for(i=1;i<=n;i++)
 59     {
 60         for(j=st[i];j!=0;j=e[j].next)
 61         {
 62             int temp=e[j].v;
 63             if(color[i]!=color[temp])
 64             {
 65                 map[++cnt].v=color[temp];
 66                 map[cnt].next=head[color[i]];
 67                    head[color[i]]=cnt;
 68             }
 69         }
 70         
 71     }
 72 }
 73 void spfa(int x)//SPFA找最長路 
 74 {
 75     memset(vis,false,sizeof(vis));
 76     int l=1,r=1;
 77     q[l]=x;//初始點放入隊列 
 78     vis[x]=true;
 79     d[x]=money[x];
 80     while(l<=r)
 81     {
 82         int u=q[l++];
 83         for(int i=head[u];i!=0;i=map[i].next)//遍歷所有以當前點為起點的邊 
 84         {
 85             int v=map[i].v;
 86             if(d[v]<d[u]+money[v])
 87             {
 88                 d[v]=d[u]+money[v];
 89                 if(vis[v])continue;
 90                 q[++r]=v;//如果當前拓展的邊的終點不在隊列里,就把它放入隊尾 
 91                 vis[v]=true;
 92             }
 93         }
 94         vis[u]=false;
 95     }
 96 }
 97 int main()
 98 {
 99     int a,b,i,s,p,o,ans=0;
100     scanf("%d%d",&n,&m);
101     for(i=1;i<=m;i++)
102     {
103         scanf("%d%d",&a,&b);
104         build(a,b);
105     }//建初始圖 
106     for(i=1;i<=n;i++)
107     {
108         if(!dfn[i])tarjan(i);//找強連通分量
109     }
110     add();//建新圖 
111     for(i=1;i<=n;i++)
112     {
113         scanf("%d",&atm[i]);
114         money[color[i]]+=atm[i];
115     }
116     scanf("%d%d",&s,&p);
117     spfa(color[s]);//找單源最短路 
118     for(i=1;i<=p;i++)
119     {
120         scanf("%d",&o);
121         ans=max(ans,d[color[o]]);//找到以酒吧為終點的最長路 
122     }
123     printf("%d",ans);
124     return 0;
125 }
APIO2009 Atm

 


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

-Advertisement-
Play Games
更多相關文章
  • 一段簡單粗糙的代碼。主要是實現的功能是模擬用戶發送簡訊的功能。 python版本3.5.2 appium版本1.4.16.1 ...
  • 成員屬性和構造方法皆為對象,通過Class對象的方法可以得到 輸出結果: ...
  • 題目:排列問題,設R={r1,r2...rn}是要進行排列的n個元素,求R的全排列perm(R); a、遞歸關係 Ri=R-{ri} perm(R)=U(ri)perm(Ri) b、終止條件:n=1時 c、參數 int k,int m 代碼如下: 運行結果如下: ...
  • 序列圖 活動圖 ...
  • 做驗證碼用到的,然後就把這個函數封裝起來,使用時候要設置2個參數: $str設置里要被採集的字元串,比如: $str='efasfgzsrhftjxjxjhsrth'; 則在函數裡面生成的字元串就回從efasfgzsrhftjxjxjhsrth裡面隨機抓取; $codeLen設置要生成的隨機字元串, ...
  • 肯定是沒有找到相關的路徑,這時候只需要在.pro文件中加入便好了,比如我要用到讀寫xml的一些頭文件,則需要在.pro中加入如下代碼: 就可以正常引用了。 ...
  • 轉載 http://www.cnblogs.com/E-star/archive/2012/08/03/2621025.html 求歐拉函數的模板: 歐拉函數打表: ...
  • 說明:一些基本的代碼我都進行了註釋,這裡實現的驗證碼位數、需要用的字元串都可以再設置。有我的註釋,大家應該很容易能看得懂。 基本思路: 1.用mt_rand()隨機生成數字確定需要獲取的字元串,對字元串進行拼接(覺得生成的驗證碼覺得有點太擠,大家可以再字元串中間拼接個空格鍵),實現隨機驗證碼; 備註 ...
一周排行
    -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.數據驗證 在伺服器端進行嚴格的數據驗證,確保接收到的數據符合預期格 ...