時空亂流
Problem:1487
Time Limit:1500ms
Memory Limit:65535K
Description
星際飛行員Alice在一次航行中遭遇了時空亂流，時空亂流將導致Alice乘坐的飛船在n個位面之間穿梭。
星際宇航局管理員Bob收到了Alice的求救信號，決定在某些位面上設立監測站，當Alice進入某個已經設立監測站的位面后，她會立即被拯救。
由于不同位面情況不同，設立監測站的花費也不相同。在第i個位面設立監測站，所需花費為Ci。
時空亂流已經被星際宇航局完全勘測，每個位面都有通往某個位面的通道，如果第i個位面沒有監測站，Alice會前往第Ai個位面。（若Ai=i則會停留在當前位面）
Bob并不知道Alice的初始位置，他必須考慮所有可能的情況，并使用盡可能少的花費，確保能從時空亂流中救出Alice。
你能幫Bob計算出至少要花費多少，才能確保能救出Alice嗎？
Input
第一行一個整數T，表示有T組測試數據。
每組測試數據，第一行一個整數n (1≤n≤200000)，表示有n個位面。
第二行n個整數Ci(1≤Ci≤10000)，表示在第i個位面設立監測站的花費Ci。
第三行n個整數Ai(1≤Ai≤n)，表示第i個位面通往第Ai個位面。
Output
每組數據輸出一個整數，表示最小花費。
Sample Input
3
5
1 2 3 2 10
1 3 4 3 3
4
1 10 2 10
2 4 2 2
7
1 1 1 1 1 1 1
2 2 2 3 6 7 6
Sample Output
3
10
2
Hint
輸入數據較多，請使用scanf/printf
Source
AotoriChiaki

分類：tarjan
用tarjan把強連通分量求出來，用一個數組min_cost記錄該強連通分量的最小花費

#include <stdio.h> #include <algorithm> #include <string.h> using namespace std; #define mem(x,y) memset(x,y,sizeof x) #define maxn 200010 #define inf 0x3f3f3f3f struct Node{int to;int next;}; Node e[maxn]; int dfn[maxn],low[maxn],stack[maxn],head[maxn],vis[maxn],belong[maxn],out[maxn],cost[maxn],min_cost[maxn]; int n,cnt,cnt1,tot,inde; void Init() {mem(head,-1);mem(out,0);mem(dfn,0);mem(low,0);mem(stack,0);mem(vis,0);cnt=cnt1=tot=inde=0;for(int i=1;i<=n;i++)min_cost[i]=inf; } void add(int x,int y) {e[++cnt].next=head[x];e[cnt].to=y;head[x]=cnt; } void tarjan(int x) {dfn[x]=low[x]=++tot;stack[++inde]=x;vis[x]=1;for(int i=head[x];i!=-1;i=e[i].next){int v=e[i].to;if(!dfn[v]){tarjan(v);low[x]=min(low[x],low[v]);}else if(vis[v])low[x]=min(low[x],dfn[v]);}if(low[x]==dfn[x]){cnt1++;while(x!=stack[inde+1]){belong[stack[inde]]=cnt1;vis[stack[inde]]=0;min_cost[cnt1]=min(min_cost[cnt1],cost[stack[inde]]);inde--;}} } int main() {int t;scanf("%d",&t);while(t--){scanf("%d",&n);Init();for(int i=1;i<=n;i++)scanf("%d",&cost[i]);for(int i=1;i<=n;i++){int xx;scanf("%d",&xx);if(i!=xx)add(i,xx);}int ans=0;for(int i=1;i<=n;i++)if(!dfn[i])tarjan(i);/*for(int i=1;i<=n;i++)if(!dfn[i])ans+=cost[i];*/for(int i=1;i<=n;i++)for(int j=head[i];j!=-1;j=e[j].next)if(belong[i]!=belong[e[j].to])out[belong[i]]++;for(int i=1;i<=cnt1;i++)if(!out[i])ans+=min_cost[i];printf("%d\n",ans);}return 0; }

總結

以上是生活随笔為你收集整理的nefuoj1487时空乱流的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。