首页 > 代码库 > UESTC 901 方老师抢银行 --Tarjan求强连通分量

UESTC 901 方老师抢银行 --Tarjan求强连通分量

2024-07-08 07:01:09   230人阅读

思路：如果出现了一个强连通分量，那么走到这个点时一定会在强连通分量里的点全部走一遍，这样才能更大。所以我们首先用Tarjan跑一遍求出所有强连通分量，然后将强连通分量缩成点（用到栈）然后就变成了一个DAG（有向无环图），然后跑一遍DFS，不断加上遍历点的权值，如果到了网吧，则更新一遍答案，因为可以出去了。

求强连通分量时，如果low[u] == dfn[u]，说明形成了一个新的强连通分量，且根为u。具体求强连通分量见：http://www.cnblogs.com/whatbeg/p/3776422.html

代码：

#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>#include <stack>using namespace std;#define N 100007struct Edge{    int v,next;}G[3*N],G2[3*N];int first[3*N],first2[3*N],low[N],dfn[N];int instk[N],bel[N],coin[N],iswb[N],wb[N],coin2[N];int tot,tot2,n,m,Time,cnt,P,K,res;stack<int> stk;void addedge(Edge *G,int& tot,int *first,int u,int v){    G[tot].v = v;    G[tot].next = first[u];    first[u] = tot++;}void Tarjan(int u){    low[u] = dfn[u] = ++Time;    stk.push(u);    instk[u] = 1;    for(int i=first[u];i!=-1;i=G[i].next)    {        int v = G[i].v;        if(!dfn[v])   //树边        {            Tarjan(v);            low[u] = min(low[u],low[v]);        }        else if(instk[v])  //回边            low[u] = min(low[u],dfn[v]);    }    if(low[u] == dfn[u])    {        cnt++;        int v;        do        {            v = stk.top();            stk.pop();            if(iswb[v])                wb[cnt] = 1;            instk[v] = 0;            coin2[cnt] += coin[v];            bel[v] = cnt;            if(v == P)                P = cnt;        }while(u != v);    }}void dfs(int u,int sum){    sum += coin2[u];    if(wb[u])        res = max(res,sum);    for(int i=first2[u];i!=-1;i=G2[i].next)    {        int v = G2[i].v;        dfs(v,sum);    }}int main(){    int i,j,u,v;    while(scanf("%d%d",&n,&m)!=EOF)    {        memset(first,-1,sizeof(first));        memset(first2,-1,sizeof(first2));        memset(G,0,sizeof(G));        memset(G2,0,sizeof(G2));        memset(iswb,0,sizeof(iswb));        memset(wb,0,sizeof(wb));        memset(instk,0,sizeof(instk));        memset(bel,-1,sizeof(bel));        memset(coin2,0,sizeof(coin2));        memset(low,0,sizeof(low));        memset(dfn,0,sizeof(dfn));        tot = tot2 = 0;        Time = cnt = 0;        while(!stk.empty())            stk.pop();        for(i=0;i<m;i++)        {            scanf("%d%d",&u,&v);            addedge(G,tot,first,u,v);        }        for(i=1;i<=n;i++)            scanf("%d",&coin[i]);        scanf("%d",&P);        scanf("%d",&K);        for(i=0;i<K;i++)        {            scanf("%d",&v);            iswb[v] = 1;        }        for(v=1;v<=n;v++)  //Tarjan求强连通分量        {            if(!dfn[v])                Tarjan(v);        }        for(i=1;i<=n;i++)   //重建为一个DAG        {            for(j=first[i];j!=-1;j=G[j].next)            {                v = bel[G[j].v];                u = bel[i];                if(u != v)  //如果相连点不是一个连通分量                    addedge(G2,tot2,first2,u,v);  //建桥            }        }        res = -1;        dfs(P,0);        printf("%d\n",res);    }    return 0;}
View Code

 


联系
我们