時間限制: 10000ms 單點時限: 1000ms 記憶體限制: 256MB
-
6 6 2 4 3 5 4 4 1 2 2 4 1 3 3 5 3 6 6 3 樣例輸出 -
13
描述
暑假到了!!小Hi和小Ho為了體驗生活，來到了住在大草原的約翰家。今天一大早，約翰因為有事要出去，就拜托小Hi和小Ho忙幫放牧。
約翰家一共有N個草場，每個草場有容量為W[i]的牧草，N個草場之間有M條單向的路徑。
小Hi和小Ho需要将牛羊群趕到草場上，當他們吃完一個草場牧草後，繼續前往其他草場。當沒有可以到達的草場或是能夠到達的草場都已經被吃光了之後，小hi和小Ho就把牛羊群趕回家。
一開始小Hi和小Ho在1号草場，在回家之前，牛羊群最多能吃掉多少牧草？
舉個例子：
圖中每個點表示一個草場，上部分數字表示編号，下部分表示草場的牧草數量w。
在1吃完草之後，小Hi和小Ho可以選擇把牛羊群趕到2或者3，假設小Hi和小Ho把牛羊群趕到2：
吃完草場2之後，隻能到草場4，當4吃完後沒有可以到達的草場，是以小Hi和小Ho就把牛羊群趕回家。
若選擇從1到3，則可以到達5，6：
選擇5的話，吃完之後隻能直接回家。若選擇6，還可以再通過6回到3，再到5。
是以該圖可以選擇的路線有3條：
1->2->4 total: 11
1->3->5 total: 9
1->3->6->3->5: total: 13
是以最多能夠吃到的牧草數量為13。
本題改編自USACO月賽金組
輸入
第1行：2個正整數，N,M。表示點的數量N，邊的數量M。1≤N≤20,000, 1≤M≤100,000
第2行：N個正整數，第i個整數表示第i個牧場的草量w[i]。1≤w[i]≤100,000
第3..M+2行：2個正整數，u,v。表示存在一條從u到v的單向路徑。1≤u,v≤N
輸出
第1行：1個整數，最多能夠吃到的牧草數量。
樣例輸入
提示：強連通分量
小Ho：我覺得這次最大的問題就是會出現環了。
小Hi：假如沒有環呢？
小Ho：那樣我就可以這麼來做：
因為不存在環，那麼圖就滿足了有向無環的性質。我可以利用上次我們解決病毒問題時同樣的思路，将累加改為求最大值，利用拓撲排序計算出從起點到目前節點能夠得到的最大牧草數量。即：
假設gress[i]表示從起點到草場i累計可以吃到的牧草數量。
grass[i] = max{ grass[j] | j 是 i的前驅結點 } + w[i] 最後我隻需要知道最大的grass[i]，就是我們所要尋求的答案。
小Hi：小Ho很厲害嘛，這麼快就學會了使用拓撲排序。
小Ho：哎嘿嘿....
小Hi：你說的沒錯，但是這次的問題最大的限制就是有環的存在。
小Ho：是以有什麼辦法能夠處理麼？
小Hi：當然有了，不過首先我們要了解一個新的知識——強連通分量，其定義為：
對于有向圖上的2個點a,b，若存在一條從a到b的路徑，也存在一條從b到a的路徑，那麼稱a,b是強連通的。
對于有向圖上的一個子圖，若子圖内任意點對(a,b)都滿足強連通，則稱該子圖為強連通子圖。
非強連通圖有向圖的極大強連通子圖，稱為強連通分量。
特别地，和任何一個點都不強連通的單個點也是一個強連通分量。
對于一個強連通的分量，也就是在其中任意一個點都可以到達其他點。如果草場滿足這個性質呢？
小Ho：如果草場是一個強連通圖，那麼我們隻要走到任意一點，就可以把其他所有的草場都走一遍，并且可以選擇任意一個點作為終點。
小Hi：沒錯，再回頭看看我們的例子：
同時存在邊(3,6)和(6,3)，是以3和6這兩個節點也就構成了一個強連通分量。在我們路徑中也就存在了3->6->3這樣一段。如果換個方式講的話：
首先到了3，在這個強連通分量中，我們将該分量中所有的點都走過了之後，又重新回到了3。
在處理的時候，我們不妨可以将6和3縮成一個點，那麼就可以得到：
這樣是不是就變成了你可以解決的問題了？
小Ho：是的，而且答案也沒有變化。也就是說我需要滿足強連通的點都縮在一起就好了，但是我怎麼确定應該縮到哪一點呢？
小Hi：因為一個強連通塊會被縮成一個點，那麼我們可以直接建立一個新的圖，這個圖中的點對應的是每一個強連通塊。若原圖中存在邊(u,v)，連接配接了屬于強連通分量A的點u和屬于強連通分量B的點v，那麼我們就在新圖中建立一條邊(A,B)。
小Ho：哦，我大概明白了。這次的問題處理方法就是先根據原圖找到所有的強連通分量，然後再根據原圖邊的關系建立新的圖，之後再用拓撲排序來處理就可以得到最終結果。
小Hi：沒錯，就是這樣。
小Ho：那麼我還有最後一個問題：我們要如何求強連通分量。
小Hi：當然，我們還是得用Tarjan算法來完成了，其僞代碼如下：
tarjan(u)
{
Dfn[u]=Low[u]=++Index // 為節點u設定次序編号和Low初值
Stack.push(u) // 将節點u壓入棧中
for each (u, v) in E // 枚舉每一條邊
if (v is not visted) // 如果節點v未被通路過
tarjan(v) // 繼續向下找
Low[u] = min(Low[u], Low[v])
else if (v in Stack) // 如果節點v還在棧内(很重要,無向圖沒有這一步)
Low[u] = min(Low[u], Dfn[v])
if (Dfn[u] == Low[u]) // 如果節點u是強連通分量的根
repeat
v = Stack.pop // 将v退棧，為該強連通分量中一個頂點
mark v // 标記v，同樣通過棧來找連通分量
until (u == v)
}
小Ho：我懂了。我這就去實作它！
小Hi：當然，别忘了還有最重要的一個條件，我們開始在草場1，是以可能有些草場我們是無法到達的，那樣的草場需要特殊處理，簡單的做法就是将草量處理為0。
小Ho：好，我知道了！
#include <iostream>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <set>
#include <queue>
#include <algorithm>
using namespace std;
#define maxn 20100
#define maxe 200100
struct node
{
int v;
int next;
}Edge[maxe],Edge2[maxe];
int dfn[maxn],low[maxn],stack[maxn],head[maxe],head2[maxe],w[maxn],belong[maxn],n,m,cnt,Index,top,cnt2;
int inDeg[maxn]; //各節點的入度
long long ans,num[maxn],ans2[maxn];
bool instack[maxn],vis[maxn][maxn],vis2[maxn];
set<int>Set;
void AddEdge(int a,int b,node *Edge,int *head)
{
Edge[cnt].v=b;
Edge[cnt].next=head[a];
head[a]=cnt++;
}
void topoSort();
void tarjan(int u)
{
int v;
dfn[u]=low[u]=++Index; // 為節點u設定次序編号和Low初值
stack[++top]=u; // 将節點u壓入棧中
instack[u]=true;
for (int i=head[u]; i!=-1; i=Edge[i].next) // 枚舉每一條邊
{
v=Edge[i].v;
if(!dfn[v]) // 如果節點v未被通路過
{
tarjan(v); // 繼續向下找
low[u]=min(low[u],low[v]);
}
else if(instack[v]) // 如果節點v還在棧内(很重要,無向圖沒有這一步)
{
low[u]=min(low[u],dfn[v]);
}
}
if (dfn[u]==low[u]) // 如果節點u是強連通分量的根
{
cnt2++;
int j;
do
{
j=stack[top--]; // 将v退棧，為該強連通分量中一個頂點
belong[j]=cnt2; //結點j屬于新結點cnt2
instack[j]=false; //重置狀态
}while (j!=u);
}
}
void dfs(int u, long long w)
{
if(ans<w)
{
ans=w;
}
for (int i=head2[u]; i!=-1; i=Edge2[i].next)
{
dfs(Edge2[i].v, w+num[Edge2[i].v]);
}
}
void ReBuild()
{
int v;
cnt=0;
for (int i=1; i<=n; i++)
{
num[belong[i]]+=w[i]; //更新縮點草的數量
if(vis2[i])
{
Set.insert(belong[i]); //将新結點存入集合中，後面會用
}
}
//重建立圖
for (int u=1; u<=n; u++)
{
for (int i=head[u]; i!=-1; i=Edge[i].next)
{
v=Edge[i].v;
if(belong[u]!=belong[v] && !vis[belong[u]][belong[v]])
{
AddEdge(belong[u], belong[v], Edge2, head2);
vis[belong[u]][belong[v]]=1;
inDeg[belong[v]]++;
}
}
}
ans=0;
dfs(belong[1], num[belong[1]]);
printf("%lld\n",ans);
// topoSort(); //使用拓撲排序始終不對
}
void Init() //初始化
{
cnt=0;
Index=0;
top=-1;
memset(head, -1, sizeof(head));
memset(head2, -1, sizeof(head2));
for (int i=0; i<=n; i++)
{
dfn[i]=0;
num[i]=0;
belong[i]=0;
instack[i]=false;
inDeg[i]=0;
ans2[i]=0;
vis2[i]=false;
}
for (int i=0; i<=n; i++)
{
for (int j=0; j<=n; j++)
{
vis[i][j]=0;
}
}
}
//拓撲排序
void topoSort()
{
queue<int>q;
for (set<int>::iterator it=Set.begin(); it!=Set.end(); ++it)
{
ans2[*it]=num[*it];
if(inDeg[*it]==0)
{
q.push(*it);
}
}
int u,v;
while (!q.empty())
{
u=q.front();
q.pop();
for (int i=head2[u]; i!=-1; i=Edge2[i].next)
{
v=Edge2[i].v;
inDeg[v]--;
ans2[v]+=ans2[u];
if (inDeg[v]==0)
{
q.push(v);
}
}
}
long long ans3=0;
for (set<int>::iterator it=Set.begin(); it!=Set.end(); ++it)
{
ans3=max(ans3,ans2[*it]);
}
printf("%lld\n",ans3);
}
void dfs2(int u) //連通性判斷
{
vis2[u]=true;
for (int i=head[u]; i!=-1; i=Edge[i].next)
{
if(!vis2[Edge[i].v])
dfs2(Edge[i].v);
}
}
int main()
{
int u,v;
Init();
scanf("%d%d",&n,&m);
for (int i=1; i<=n; i++)
{
scanf("%d",&w[i]);
}
for (int i=0; i<m; i++)
{
scanf("%d%d",&u,&v);
AddEdge(u,v,Edge,head);
}
dfs2(1); //檢查圖的連通性
for (int i=1; i<=n; i++)
{
if (!vis2[i]) //将和結點1沒有連通的點的權值置0
{
w[i]=0;
}
}
tarjan(1);
ReBuild();
return 0;
}
使用dfs計算最後結果的是對的，但是用拓撲排序始終不對，這個還待解決。