Description 
Input
第一行包含兩個整數N、M。N表示路口的個數，M表示道路條數。接下來M行，每行兩個整數，這兩個整數都在1到N之間，第i+1行的兩個整數表示第i條道路的起點和終點的路口編號。接下來N行，每行一個整數，按順序表示每個路口處的ATM機中的錢數。接下來一行包含兩個整數S、P，S表示市中心的編號，也就是出發的路口。P表示酒吧數目。接下來的一行中有P個整數，表示P個有酒吧的路口的編號 Output
輸出一個整數，表示Banditji從市中心開始到某個酒吧結束所能搶劫的最多的現金總數。 Sample Input 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 Sample Output 47 HINT
50%的輸入保證N, M<=3000。所有的輸入保證N, M<=500000。每個ATM機中可取的錢數為一個非負整數且不超過4000。輸入數據保證你可以從市中心沿著Siruseri的單向的道路到達其中的至少一個酒吧。
解題方法： 首先進行強連通縮點，維護每一個連通分量中，是否有一個點是酒吧，以及總錢數的多少。對縮點后的圖進行拓撲排序，然后按照拓撲排序進行動態規劃。記 dp[i]表示走到點 i 的最大獲利，對于給定的起點屬于的連通塊有 dp[i]＝money[i]，其余點的初值都是 dp[i]＝負無窮。對于一條邊 i 連接 j，我們用 dp[i]＋money[j]來更新 dp[j]。答案是滿足一個連通塊中至少有一個是酒吧的強連通分量中最大的 dp[i]。由于會爆棧，強連通分量算法要進行人工堆棧。時間復雜度 O(n＋m)。
//bzoj 1179 tarjan spfa#include <bits/stdc++.h>using namespace std;const int maxn = 500005;int n, m, q, S, dfs_clock, cnt, scc, top, ans;int head1[maxn], head2[maxn], dp[maxn];int dfn[maxn], low[maxn], c[maxn], v[maxn], s[maxn], belong[maxn];bool inq[maxn], vis[maxn];struct edge{ int v, nxt; edge(){} edge(int v, int nxt) : v(v), nxt(nxt) {}}E1[maxn*2], E2[maxn*2];void init1(){ cnt = 0; memset(dp, 0, sizeof(dp)); memset(head1, -1, sizeof(head1));}void init2(){ cnt = 0; memset(head2, -1, sizeof(head2));}void addedge1(int u, int v){ E1[cnt].v = v, E1[cnt].nxt = head1[u], head1[u] = cnt++;}void addedge2(int u, int v){ E2[cnt].v = v, E2[cnt].nxt = head2[u], head2[u] = cnt++;}void tarjan(int x){ int now = 0; dfn[x] = low[x] = ++dfs_clock; s[++top] = x; inq[x] = 1; for(int i = head1[x]; ~i; i = E1[i].nxt){ int to = E1[i].v; if(!dfn[to]){ tarjan(to); low[x] = min(low[x], low[to]); } else if(inq[to]){ low[x] = min(low[x], dfn[to]); } } if(low[x] == dfn[x]){ scc++; while(now != x){ now = s[top]; top--; belong[now] = scc; v[scc] += c[now]; inq[now] = 0; } }}void rebuild(){ init2(); for(int i = 1; i <= n; i++){ for(int j = head1[i]; ~j; j = E1[j].nxt){ int to = E1[j].v; if(belong[i] != belong[to]){ addedge2(belong[i], belong[to]); } } }}void spfa(){ queue <int> que; que.push(belong[S]); vis[belong[S]] = 1; dp[belong[S]] = v[belong[S]]; while(!que.empty()){ int now = que.front(); que.pop(); vis[now] = 0; for(int i = head2[now]; ~i; i = E2[i].nxt){ int to = E2[i].v; if(dp[now] + v[to] > dp[to]){ dp[to] = dp[now] + v[to]; if(!vis[to]){ vis[to] = 1; que.push(to); } } } }}int main(){ init1(); scanf("%d%d", &n, &m); for(int i = 1; i <= m; i++){ int u, v; scanf("%d%d", &u, &v); addedge1(u, v); } for(int i = 1; i <= n; i++) scanf("%d", &c[i]); for(int i = 1; i <= n; i++) if(!dfn[i]) tarjan(i); scanf("%d%d", &S, &q); rebuild(); spfa(); for(int i = 1; i <= q; i++){ int x; scanf("%d", &x); if(dp[belong[x]] > ans) ans = dp[belong[x]]; }新聞熱點
疑難解答
