洛谷p3387
思路:
算法:tarjan算法
根據題意,我們只要找到一個路徑,使得最終權重最大即可,首先,根據題目可知,如果一個點在一個環上,那么我們就將這整個環都選上,題目上允許我們能夠重復走,因此,我們可以將環縮成點,將環所稱點后,就可以轉換成樹,從沒有父節點的結點開始,我們向下走,每遍歷一個子結點,就將子節點更新一次,最終取結點的最大值即可
#include<bits/stdc++.h>using namespace std;int n,m;const int N=1e4+19;const int M=1e5+10;vector<int>vec[N];int a[N];int siz[N];int cnt;int dfn[N],low[N],tot;int p[N];int scc[N];int inDegree[N];stack<int>sta;//tarjan模板 void tarjan(int x){low[x]=dfn[x]=++tot;sta.push(x);for(auto y:vec[x]){if(dfn[y]==0){tarjan(y);low[x]=min(low[x],low[y]);}else if(!scc[y]){low[x]=min(low[x],dfn[y]);}}if(low[x]==dfn[x]){cnt++;while(1){int y=sta.top();sta.pop();siz[cnt]++;p[cnt]+=a[y];//記錄每個環的總權重scc[y]=cnt;if(y==x)break;}}}struct edge{int from;int to;}e[M];vector<int>ve[N];int ans[N];int s;int res=0;//topo算法
void solve(){queue<int>q;for(int i=1;i<=cnt;i++){ans[i]=p[i];//尋找沒有入讀的環if(!inDegree[i])q.push(i);}while(q.empty()==false){int x=q.front();q.pop();for(auto y:ve[x]){
//從沒有入度的環開始,向下遍歷它出度的環
//入度的環的最大值等于指向它的環的最大值加上它自己的權重ans[y]=max(ans[y],p[y]+ans[x]);
//處理一個入度的邊就減去一個邊inDegree[y]--;
//如果入度的點最終沒有邊指向它,那么代表它就成了一個根結點,那么,就將他放入隊列中if(inDegree[y]==0)q.push(y);}}for(int i=1;i<=cnt;i++){res=max(res,ans[i]);}cout<<res<<endl;}int main(void){cin>>n>>m;for(int i=1;i<=n;i++)cin>>a[i];for(int i=1;i<=m;i++){int a,b;cin>>a>>b;
//記錄邊的原因是為了后序我們進行環與環的入度操作時候,可以直接遍歷邊e[i].from=a;e[i].to=b;vec[a].push_back(b);}for(int i=1;i<=n;i++){if(!dfn[i])tarjan(i);}for(int i=1;i<=m;i++){
//記入環與環之間相連的邊int fr=scc[e[i].from];int tr=scc[e[i].to];if(fr==tr)continue;
//記入入度的邊inDegree[tr]++;ve[fr].push_back({tr});}solve();}
)
