tarjan【模板】缩点

传送门：https://www.luogu.org/problemnew/show/P3387

首先呢，tarjan找一个图的强连通分量是基于对图的dfs的。这中间开了一个dfn[]代表dfs序，还有个low[]代表该节点在dfs形成的树中能到达的最近的根。然后分情况进行更新（一会儿看我代码吧）。

为了记录一个强联通分量，我们还要在开一个栈来储存当前查找的强连通分量。如果low[x] == dfn[x]，那就说明这个点在dfs树种不能往上再爬了，于是就开始弹栈。

对于这道题呢，先用tarjan找出强联通分量，然后缩点建立新图。可以发现，建立的新图是一个拓扑图，所以可以拓扑排序后在图上dp，然而我这么写wa了。翻题解的时候看到了一个更简单的方法：记录每一个点的入度，对于每一个入度为0的点用spfa跑一遍最长路，然后在所有最长路中取一个max即可。

 #include<cstdio>

 #include<iostream>

 #include<cstring>

 #include<cmath>

 #include<algorithm>

 #include<cctype>

 #include<vector>

 #include<stack>

 #include<queue>

 using namespace std;

 #define enter printf("\n")

 #define space printf(" ")

 #define Mem(a) memset(a, 0, sizeof(a))

 typedef long long ll;

 typedef double db;

 const int INF = 0x3f3f3f3f;

 const db eps = 1e-;

 const int maxn = 1e5 + ;

 inline ll read()

 {

     ll ans = ;

     char ch = getchar(), last = ' ';

     while(!isdigit(ch)) {last = ch; ch = getchar();}

     while(isdigit(ch))

     {

         ans = ans *  + ch - ''; ch = getchar();

     }

     if(last == '-') ans = -ans;

     return ans;

 }

 inline void write(ll x)

 {

     if(x < ) x = -x, putchar('-');

     if(x >= ) write(x / );

     putchar('' + x % );

 }

 vector<int> v[maxn];

 int n, m, a[maxn];

 int dfn[maxn], low[maxn], cnt = ;

 bool in[maxn];

 stack<int> st;

 int col[maxn], ccol = , val[maxn];

 void tarjan(int now)

 {

     dfn[now] = low[now] = ++cnt;

     st.push(now); in[now] = ;

     for(int i = ; i < (int)v[now].size(); ++i)

     {

         if(!dfn[v[now][i]])                    //这个联通块还没找完

         {

             tarjan(v[now][i]);

             low[now] = min(low[now], low[v[now][i]]);

         }

         else if(in[v[now][i]]) low[now] = min(low[now], dfn[v[now][i]]);    //这个点找到了他所在联通块的祖先节点

     }

     if(low[now] == dfn[now])        //开始找出联通块中的所有点

     {

         int x; ccol++;            //ccol相当于染色种数，也就是有多少个连通分量

         do

         {

             x = st.top();

             in[x] = ; st.pop();

             col[x] = ccol; val[ccol] += a[x];    //val[]记录新图上的点的点权

         }while(x != now);

     }

     return;

 }

 vector<int> v2[maxn];

 bool du[maxn];

 void newGraph(int now)

 {

     for(int i = ; i < (int)v[now].size(); ++i)

     {

         int x = col[now], y = col[v[now][i]];

         if(x == y) continue;        //别忘了两个点在一个联通块的情况

         v2[x].push_back(y);

         du[y] = ;

     }

     return;

 }

 int ans = ;

 int dis[maxn];

 bool vis[maxn];

 void spfa(int s)

 {

     Mem(vis);

     for(int i = ; i <= ccol; ++i) dis[i] = -INF;

     queue<int> q;

     q.push(s); vis[s] = ;

     dis[s] = val[s];

     while(!q.empty())

     {

         int now = q.front(); q.pop(); vis[now] = ;

         for(int i = ; i < (int)v2[now].size(); ++i)

         {

             if(dis[now] + val[v2[now][i]] > dis[v2[now][i]])

             {

                 dis[v2[now][i]] = dis[now] + val[v2[now][i]];

                 if(!vis[v2[now][i]]) {q.push(v2[now][i]); vis[v2[now][i]] = ;}

             }

         }

     }

     for(int i = ; i <= ccol; ++i) ans = max(ans, dis[i]);        //更新答案

 }

 int main()

 {

     n = read(); m = read();

     for(int i = ; i <= n; ++i) a[i] = read();

     for(int i = ; i <= m; ++i)

     {

         int x = read(), y = read();

         v[x].push_back(y);

     }

     for(int i = ; i <= n; ++i) if(!dfn[i]) tarjan(i);        //有的点从一个定点出发可能走不到，就都得判断是否走过

     for(int i = ; i <= n; ++i) newGraph(i);                //建立新图

     for(int i = ; i <= ccol; ++i) if(!du[i]) spfa(i);        //对于每一个入度为0的点，跑最长路

     write(ans); enter;

     return ;

 }

巴特西

tarjan【模板】缩点

最新文章

热门文章