[关闭]
@DATASOURCE 2015-09-01T22:19:59.000000Z 字数 12423 阅读 1555

图的连通性问题

图论 连通性

割点的求法(无向图)

  1. void Tarjan(int u, int fa){
  2.     int son = 0;
  3.     vis[u] = 1;
  4.     dfn[u] = low[u] = ++tdfn;
  5.     for(int i = head[u]; i + 1; i = edge[i].nxt){
  6.         int v = edge[i].v;
  7.         if(vis[v] == 1 && v != fa) low[u] = min(low[u], dfn[v]);
  8.         if(vis[v]) continue;
  9.         Tarjan(v, u);
  10.         son++;
  11.         low[u] = min(low[u], low[v]);
  12.         if((u == root && son > 1) || (u != root && dfn[u] <= low[v])) cut[u] = 1;
  13.     }
  14.     vis[u] = 2;
  15. }

调用时root = 1, Tarjan(1, -1).

割点删除后图的连通分支数

  1. // 当 cut[i] > 0 时有割点， 并且删除改点后， 图被分成 cut[i] + 1 个连通分量。
  2. void Tarjan(int u){
  3.     vis[u] = 1;
  4.     int son = 0;
  5.     dfn[u] = low[u] = ++tdfn;
  6.     for(int i = head[u]; i + 1; i = edge[i].nxt){
  7.         int v = edge[i].v;
  8.         if(vis[v]) low[u] = min(low[u], dfn[v]);
  9.         else{
  10.             Tarjan(v);
  11.             low[u] = min(low[u], low[v]);
  12.             if(dfn[u] <= low[v]) cut[u]++, son++;
  13.         }
  14.     }
  15.     if(u == rt) cut[u] = son - 1 < 0 ? 0 : son - 1;
  16. }

调用时rt = 1, Tarjan(1).

另一种写法

  1. // 当 cut[i] > 0 时有割点， 并且删除改点后， 图被分成 cut[i] + 1 个连通分量。
  2. void Tarjan(int u, int fa){
  3.     vis[u] = 1;
  4.     int son = 0;
  5.     dfn[u] = low[u] = tdfn++;
  6.     for(int i = head[u]; i + 1; i = edge[i].nxt){
  7.         int v = edge[i].v;
  8.         if(vis[v] == 1 && v != fa) low[u] = min(low[u], dfn[v]);
  9.         if(vis[v]) continue;
  10.         Tarjan(v, u);
  11.         son++;
  12.         low[u] = min(low[u], low[v]);
  13.         if((u == rt && son > 1) || (u != rt && dfn[u] <= low[v])) cut[u]++;
  14.     }
  15.     vis[u] = 2;
  16. }

调用时rt = 1, Tarjan(1, -1);.

一个例题（POJ 2117)

题意：一个无向图，现在要去掉其中一个点，要求去掉这个点之后，总连通分支数最大。

  1. /*=============================================================================
  2. # Author:           He Shuwei
  3. # Last modified:    2015-08-03 20:37
  4. # Filename:         POJ_2117_割点.cpp
  5. # Description: 
  6. =============================================================================*/
  8. #include <map>
  9. #include <cmath>
  10. #include <queue>
  11. #include <stack>
  12. #include <vector>
  13. #include <cstdio>
  14. #include <string>
  15. #include <cstdlib>
  16. #include <cstring>
  17. #include <iostream>
  18. #include <algorithm>
  19. #define lson l, mid, ls
  20. #define rson mid, r, rs
  21. #define ls (rt << 1) + 1
  22. #define rs (rt << 1) + 2
  23. using namespace std;
  24. const int MAXN = 10100;
  26. struct Edge{
  27.     int v, nxt;
  28. };
  30. int root;
  31. int dfn[MAXN];
  32. int low[MAXN];
  33. int cut[MAXN];
  34. int vis[MAXN];
  35. int head[MAXN];
  36. Edge edge[3 * MAXN];
  37. int ecnt, n, m, tdfn;
  39. void init(){
  40.     ecnt = 0;
  41.     memset(vis, 0, sizeof(vis));
  42.     memset(dfn, 0, sizeof(dfn));
  43.     memset(cut, 0, sizeof(cut));
  44.     memset(low, 0, sizeof(low));
  45.     memset(edge, 0, sizeof(edge));
  46.     memset(head, -1, sizeof(head));
  47. }
  49. void addEdge(int u, int v){
  50.     edge[ecnt].v = v;
  51.     edge[ecnt].nxt = head[u];
  52.     head[u] = ecnt++;
  53. }
  55. void Tarjan(int u, int fa){
  56.     int son = 0;
  57.     vis[u] = 1;
  58.     dfn[u] = low[u] = ++tdfn;
  59.     for(int i = head[u]; i + 1; i = edge[i].nxt){
  60.         int v = edge[i].v;
  61.         if(vis[v] == 1 && v != fa) low[u] = min(low[u], dfn[v]);
  62.         if(vis[v]) continue;
  63.         Tarjan(v, u);
  64.         son++;
  65.         low[u] = min(low[u], low[v]);
  66.         if((u == root && son > 1) || (u != root && dfn[u] <= low[v])) cut[u]++;
  67.     }
  68.     vis[u] = 2;
  69. }
  71. int main(){
  72.     while(~scanf("%d%d", &n, &m)){
  73.         if(!(n + m)) break;
  74.         if(m == 0){
  75.             printf("%d\n", n - 1);
  76.             continue;
  77.         }
  78.         init();
  79.         int u, v;
  80.         for(int i = 0; i < m; i++){
  81.             scanf("%d%d", &u, &v);
  82.             addEdge(u, v);
  83.             addEdge(v, u);
  84.         }
  85.         int ans = 0;
  86.         int res = 0;
  87.         for(int i = 0; i < n; i++){
  88.             if(!dfn[i]){
  89.                 ans++;
  90.                 tdfn = 0;
  91.                 root = i;
  92.                 Tarjan(i, -1);
  93.             }
  94.             res = max(res, cut[i]);
  95.         }
  96.         printf("%d\n", ans + res);
  97.     }
  98.     return 0;
  99. }

求割边

  1. // edge[i].id == -1 时， 这条边是重边, 故排除
  2. // 割边的编号保存在 res 数组中。
  3. void addEdge(int u, int v, int id){
  4.     for(int i = head[u]; i + 1; i = edge[i].nxt){
  5.         if(edge[i].v == v){
  6.             edge[i].id = -1;
  7.             return;
  8.         }
  9.     }
  10.     edge[ecnt].v = v;
  11.     edge[ecnt].id = id;
  12.     edge[ecnt].nxt = head[u];
  13.     head[u] = ecnt++;
  14.     u = u ^ v, v = u ^ v, u = u ^ v;
  15.     edge[ecnt].v = v;
  16.     edge[ecnt].id = id;
  17.     edge[ecnt].nxt = head[u];
  18.     head[u] = ecnt++;
  19. }
  21. void Tarjan(int u, int fa){
  22.     vis[u] = 1;
  23.     dfn[u] = low[u] = ++tdfn;
  24.     for(int i = head[u]; i + 1; i = edge[i].nxt){
  25.         int v = edge[i].v;
  26.         if(vis[v] == 1 && v != fa) low[u] = min(low[u], dfn[v]);
  27.         if(vis[v]) continue;
  28.         Tarjan(v, u);
  29.         low[u] = min(low[u], low[v]);
  30.         if(dfn[u] < low[v] && edge[i].id != -1) res[cnt++] = edge[i].id;
  31.     }
  32.     vis[u] = 2;
  33. }

双联通缩点

  1. void Tarjan(int u, int fa){
  2.     sta.push(u);
  3.     instack[u] = true;
  4.     low[u] = dfn[u] = ++tdfn;
  5.     for(int i = head[u]; i + 1; i = edge[i].nxt){
  6.         int v = edge[i].v;
  7.         if(v == fa) continue;
  8.         if(!dfn[v]){
  9.             Tarjan(v, u);
  10.             low[u] = min(low[u], low[v]);
  11.         }else if(instack[v]) low[u] = min(low[u], low[v]);
  12.     }
  13.     if(dfn[u] == low[u]){
  14.         scc++;
  15.         int top;
  16.         do{
  17.             top = sta.top();
  18.             sta.pop();
  19.             instack[top] = false;
  20.             belong[top] = scc;
  21.         }while(top != u && !sta.empty());
  22.     }
  23. }

调用时

  1. for(int i = 1; i <= n; i++)
  2. if(!dfn[i]) Tarjan(i, -1);

一个例题（poj 3117)

题意：有n个牧场，Bessie 要从一个牧场到另一个牧场，要求至少要有2条独立的路可以走。现已有m条路，求至少要新建多少条路，使得任何两个牧场之间至少有两条独立的路。两条独立的路是指：没有公共边的路，但可以经过同一个中间顶点。

分析：在同一个边双连通分量中，任意两点都有至少两条独立路可达，所以同一个边双连通分量里的所有点可以看做同一个点。

缩点后，新图是一棵树，树的边就是原无向图的桥。

现在问题转化为：在树中至少添加多少条边能使图变为双连通图。

结论：添加边数=（树中度为1的节点数+1）/2

具体方法为，首先把两个最近公共祖先最远的两个叶节点之间连接一条边，这样可以把这两个点到祖先的路径上所有点收缩到一起，因为一个形成的环一定是双连通的。然后再找两个最近公共祖先最远的两个叶节点，这样一对一对找完，恰好是(leaf+1)/2次，把所有点收缩到了一起。

其实求边双连通分量和求强连通分量差不多，每次访问点的时候将其入栈，当low[u]==dfn[u]时就说明找到了一个连通的块，则栈内的所有点都属于同一个边双连通分量，因为无向图要见反向边，所以在求边双连通分量的时候，遇到反向边跳过就行了

  1. /*=============================================================================
  2. # Author:           He Shuwei
  3. # Last modified:    2015-08-07 14:37
  4. # Filename:         POJ_3177_3352_双连通图+缩点.cpp
  5. # Description: 
  6. =============================================================================*/
  8. #include <map>
  9. #include <cmath>
  10. #include <queue>
  11. #include <stack>
  12. #include <vector>
  13. #include <cstdio>
  14. #include <string>
  15. #include <cstdlib>
  16. #include <cstring>
  17. #include <iostream>
  18. #include <algorithm>
  19. #define lson l, mid, ls
  20. #define rson mid, r, rs
  21. #define ls (rt << 1) + 1
  22. #define rs (rt << 1) + 2
  23. using namespace std;
  24. const int MAXN = 5050;
  25. const int MAXE = 20020;
  27. struct Edge{
  28.     int v, nxt;
  29. };
  31. Edge edge[MAXE];
  32. stack <int> sta;
  33. bool instack[MAXN];
  34. int ecnt, n, m, scc, tdfn;
  35. int degree[MAXN], belong[MAXN];
  36. int head[MAXN], dfn[MAXN], low[MAXN];
  38. void init(){
  39.     ecnt = scc = tdfn = 0;
  40.     while(!sta.empty()) sta.pop();
  41.     memset(dfn, 0, sizeof(dfn));
  42.     memset(low, 0, sizeof(low));
  43.     memset(edge, 0, sizeof(edge));
  44.     memset(head, -1, sizeof(head));
  45.     memset(degree, 0, sizeof(degree));
  46.     memset(instack, 0, sizeof(instack));
  47. }
  49. void addEdge(int u, int v){
  50.     edge[ecnt].v = v;
  51.     edge[ecnt].nxt = head[u];
  52.     head[u] = ecnt++;
  53. }
  55. void Tarjan(int u, int fa){
  56.     sta.push(u);
  57.     instack[u] = true;
  58.     low[u] = dfn[u] = ++tdfn;
  59.     for(int i = head[u]; i + 1; i = edge[i].nxt){
  60.         int v = edge[i].v;
  61.         if(v == fa) continue;
  62.         if(!dfn[v]){
  63.             Tarjan(v, u);
  64.             low[u] = min(low[u], low[v]);
  65.         }else if(instack[v]) low[u] = min(low[u], low[v]);
  66.     }
  67.     if(dfn[u] == low[u]){
  68.         scc++;
  69.         int top;
  70.         do{
  71.             top = sta.top();
  72.             sta.pop();
  73.             instack[top] = false;
  74.             belong[top] = scc;
  75.         }while(top != u && !sta.empty());
  76.     }
  77. }
  79. int solve(){
  80.     for(int i = 1; i <= n; i ++)
  81.         if(!dfn[i]) Tarjan(1, -1);
  82.     for(int i = 1; i <= n; i++){
  83.         for(int j = head[i]; j + 1; j = edge[j].nxt){
  84.             int v = edge[j].v;
  85.             if(belong[i] != belong[v]) degree[belong[i]]++;
  86.         }
  87.     }
  88.     int res = 0;
  89.     for(int i = 1; i <= n; i++)
  90.         if(degree[i] == 1) res++;
  91.     int ans = (res + 1) / 2;
  92.     return ans;
  93. }
  95. int main(){
  96.     while(scanf("%d%d", &n, &m) != EOF){
  97.         init();
  98.         int u, v;
  99.         for(int i = 0; i < m; i++){
  100.             scanf("%d%d", &u, &v);
  101.             addEdge(u, v);
  102.             addEdge(v, u);
  103.         }
  104.         int ans = solve();
  105.         printf("%d\n", ans);
  106.     }
  107.     return 0;
  108. }

强连通分量

解法一

  1. void dfs(int u){
  2.     vis[u] = true;
  3.     for(int i = head[u]; i + 1; i = edge[i].nxt)
  4.         if(!vis[edge[i].v]) dfs(edge[i].v);
  5.     vs[vscnt++] = u;
  6. }
  8. void rdfs(int u, int k){
  9.     vis[u] = true;
  10.     cmp[u] = k;
  11.     for(int i = rhead[u]; i + 1; i = redge[i].nxt)
  12.         if(!vis[redge[i].v]) rdfs(redge[i].v, k);
  13. }
  15. int scc(){
  16.     memset(vis, 0, sizeof(vis));
  17.     vscnt = 0;
  18.     for(int i = 1; i <= n; i++)
  19.         if(!vis[i]) dfs(i);
  21.     int scc_cnt = 0;
  22.     memset(vis, 0, sizeof(vis));
  23.     for(int i = vscnt - 1; i >= 0; i--)
  24.         if(!vis[vs[i]]) rdfs(vs[i], scc_cnt++);
  26.     return scc_cnt;
  27. }

解法二

  2. void Tarjan(int u){
  3.     sta.push(u);
  4.     instack[u] = true;
  5.     dfn[u] = low[u] = ++tdfn;
  6.     for(int i = head[u]; i + 1; i = edge[i].nxt){
  7.         int v = edge[i].v;
  8.         if(dfn[v] == 0){
  9.             Tarjan(v);
  10.             low[u] = min(low[u], low[v]);
  11.         }else if(instack[v]) low[u] = min(low[u], low[v]);
  12.     }
  13.     if(low[u] == dfn[u]){
  14.         int top;
  15.         scc_cnt++;
  16.         do{
  17.             top = sta.top();
  18.             sta.pop();
  19.             instack[top] = false;
  20.             belong[top] = scc_cnt;
  21.         }while(u != top && !sta.empty());
  22.     }
  23. }

调用方法

  1. for(int i = 1; i <= n; i++)
  2. if(!dfn[i]) Tarjan(i);

几个例题

HDU 4635

题意：最多加多少条边，使得原图不是强连通图

正向考虑有困难，不妨反向思考，既最少去掉几条边使得原图不是强连通。

总边数sum=n*(n-1)时肯定是强连通，已经给了m条边，sum-=m

这时把已经强连通的部分进行缩点，对于缩好的点我们把他们分成两部分，保证其中一部分到另一部分没有边（这两部分不强连通），再把sum减去两部分能构成所有的边数，取最大值即为答案

具体做时枚举每个小强连通块，找到num[i]*(n-num[i])最小的情况（num[i]为小强连通块点数），其中必须出度或入度为0的连通块才可以被选择

  1. /*=============================================================================
  2. # Author:           He Shuwei
  3. # Last modified:    2015-08-08 15:47
  4. # Filename:         HDU_4635_加最多边使不强连通.cpp
  5. # Description: 
  6. =============================================================================*/
  8. #include <map>
  9. #include <cmath>
  10. #include <queue>
  11. #include <stack>
  12. #include <vector>
  13. #include <cstdio>
  14. #include <string>
  15. #include <cstdlib>
  16. #include <cstring>
  17. #include <iostream>
  18. #include <algorithm>
  19. #define lson l, mid, ls
  20. #define rson mid, r, rs
  21. #define ls (rt << 1) + 1
  22. #define rs (rt << 1) + 2
  23. using namespace std;
  24. const int MAXN = 100020;
  25. const int MAXE = 200010;
  27. struct Edge{
  28.     int v, nxt;
  29. };
  31. bool vis[MAXN];
  32. Edge edge[MAXE], redge[MAXE];
  33. int n, m, ecnt, recnt, vs_cnt, scc_cnt;
  34. int head[MAXN], rhead[MAXN], vs[MAXN], belong[MAXN], In[MAXN], Out[MAXN], num[MAXN];
  37. void init(){
  38.     ecnt = recnt = vs_cnt = scc_cnt = 0;
  39.     memset(In, 0, sizeof(In));
  40.     memset(Out, 0, sizeof(Out));
  41.     memset(num, 0, sizeof(num));
  42.     memset(edge, 0, sizeof(edge));
  43.     memset(head, -1, sizeof(head));
  44.     memset(redge, 0, sizeof(redge));
  45.     memset(rhead, -1, sizeof(rhead));
  46. }
  48. void addEdge(int *head, Edge *edge, int u, int v, int &cnt){
  49.     edge[cnt].v = v;
  50.     edge[cnt].nxt = head[u];
  51.     head[u] = cnt++;
  52. }
  54. void dfs(int u){
  55.     vis[u] = true;
  56.     for(int i = head[u]; i + 1; i = edge[i].nxt){
  57.         if(!vis[edge[i].v]) dfs(edge[i].v);
  58.     }
  59.     vs[vs_cnt++] = u;
  60. }
  62. void rdfs(int u, int k){
  63.     vis[u] = true;
  64.     belong[u] = k;
  65.     for(int i = rhead[u]; i + 1; i = redge[i].nxt){
  66.         if(!vis[redge[i].v]) rdfs(redge[i].v, k);
  67.     }
  68. }
  70. void scc(){
  71.     memset(vis, 0, sizeof(vis));
  72.     for(int i = 1; i <= n; i++)
  73.         if(!vis[i]) dfs(i);
  75.     memset(vis, 0, sizeof(vis));
  76.     for(int i = vs_cnt - 1; i >= 0; i--)
  77.         if(!vis[vs[i]]) rdfs(vs[i], scc_cnt++);
  78. }
  80. void calDegree(){
  81.     for(int u = 1; u <= n; u++){
  82.         for(int i = head[u]; i + 1; i = edge[i].nxt){
  83.             int v = edge[i].v;
  84.             if(belong[u] != belong[v]) In[belong[v]]++, Out[belong[u]]++;
  85.         }
  86.     }
  87. }
  89. long long solve(){
  91.     scc();
  93.     calDegree();
  95.     for(int i = 1; i <= n; i++)
  96.         num[belong[i]]++;
  98.     long long sss = (long long)n * (n - 1) - m;
  99.     long long ans = 0;
  100.     for(int i = 0; i < scc_cnt; i++)
  101.         if(In[i] == 0 || Out[i] == 0)
  102.             ans = max(ans, sss - (long long)num[i] * (n - num[i]));
  104.     return scc_cnt == 1 ? -1 : ans;
  105. }
  107. int main(){
  108.     int t;
  109.     scanf("%d", &t);
  110.     for(int Case = 1; Case <= t; Case++){
  111.         init();
  112.         scanf("%d%d", &n, &m);
  113.         int u, v;
  114.         for(int i = 0; i < m; i++){
  115.             scanf("%d%d", &u, &v);
  116.             addEdge(head, edge, u, v, ecnt);
  117.             addEdge(rhead, redge, v, u, recnt);
  118.         }
  120.         long long ans = solve();
  121.         printf("Case %d: %lld\n", Case, ans);
  122.     }
  123.     return 0;
  124. }

POJ3592

题目大意：

    给出一个n*m的格子地图，每一格上面是0~9，“*”或“#”。如果格子上是数字代表这个格子上有当前数量的矿石。如果是“*” 代表着当前格子是一个传送阵可以传送到指定的地方。如果是“#”代表当前格子不可达。

    现在有一个矿车在坐标（0，0），也就是左上角。他只能向右和下行驶。当遇到传送阵时可以被传送到指定的位置。当他遇到数字时就可以得到那些数量的矿石，那个地方的矿石数量就变为“0”。问矿车最多可以采多少矿。

解题思路：

    1、我们先要根据格子地图建图。（注1）

    2、因为建立出的图可能会有环，我们要用Tarjan算法将环缩成点。（注2）

    3、我们将缩点处理后的图重新建图。（注3）

    4、对图求最长路。

  1. /*=============================================================================
  2. # Author:           He Shuwei
  3. # Last modified:    2015-08-12 10:35
  4. # Filename:         POJ_3592_缩点+SPFA.cpp
  5. # Description: 
  6. =============================================================================*/
  8. #include <map>
  9. #include <cmath>
  10. #include <queue>
  11. #include <stack>
  12. #include <vector>
  13. #include <cstdio>
  14. #include <string>
  15. #include <cstdlib>
  16. #include <cstring>
  17. #include <iostream>
  18. #include <algorithm>
  19. #define lson l, mid, ls
  20. #define rson mid, r, rs
  21. #define ls (rt << 1) + 1
  22. #define rs (rt << 1) + 2
  23. using namespace std;
  24. const int MAXN = 2000;
  25. const int MAXE = 5000;
  27. struct Edge{
  28.     int v, nxt;
  29. };
  31. char mp[MAXN][MAXN];
  33. Edge edge[MAXE];
  34. stack <int> sta;
  35. bool instack[MAXN];
  36. int n, m, scc_cnt, ecnt, tdfn;
  37. int head[MAXN], val[MAXN], dfn[MAXN], low[MAXN], belong[MAXN];
  39. int scnt;
  40. bool vis[MAXN];
  41. Edge sedge[MAXE];
  42. int shead[MAXN], sccval[MAXN], dis[MAXN];
  44. void init(){
  45.     scc_cnt = ecnt = tdfn = scnt = 0;
  46.     memset(vis, 0, sizeof(vis));
  47.     memset(dis, 0, sizeof(dis));
  48.     memset(val, 0, sizeof(val));
  49.     memset(dfn, 0, sizeof(dfn));
  50.     memset(low, 0, sizeof(low));
  51.     while(!sta.empty()) sta.pop();
  52.     memset(edge, 0, sizeof(edge));
  53.     memset(head, -1, sizeof(head));
  54.     memset(sedge, 0, sizeof(sedge));
  55.     memset(shead, -1, sizeof(shead));
  56.     memset(sccval, 0, sizeof(sccval));
  57.     memset(belong, 0, sizeof(belong));
  58.     memset(instack, 0, sizeof(instack));
  59. }
  61. void addEdge(int *head, Edge *edge, int u, int v, int &cnt){
  62.     edge[cnt].v = v;
  63.     edge[cnt].nxt = head[u];
  64.     head[u] = cnt++;
  65. }
  67. void Input(){
  68.     scanf("%d%d", &n, &m);
  69.     for(int i = 0; i < n; i++)
  70.         scanf("%s", mp[i]);
  71.     int a, b;
  72.     for(int i = 0; i < n; i++)
  73.         for(int j = 0; j < m; j++){
  74.             if(mp[i][j] == '#') continue;
  75.             if(mp[i][j] >= '0' && mp[i][j] <= '9') val[m * i + j] = mp[i][j] - '0';
  76.             else if(mp[i][j] == '*'){
  77.                 scanf("%d%d", &a, &b);
  78.                 addEdge(head, edge, m * i + j, a * m + b, ecnt);
  79.             }
  81.             if(i + 1 < n && mp[i + 1][j] != '#')
  82.                 addEdge(head, edge, m * i + j, m * (i + 1) + j, ecnt);
  83.             if(j + 1 < m && mp[i][j + 1] != '#')
  84.                 addEdge(head, edge, m * i + j, m * i + j + 1, ecnt);
  85.         }
  87.     //for(int i = 0; i < n * m; i++)
  88.         //cerr <<"i = "<< i <<", val[i] = "<< val[i] << endl;
  89. }
  91. void Tarjan(int u){
  92.     sta.push(u);
  93.     instack[u] = true;
  94.     dfn[u] = low[u] = ++tdfn;
  95.     for(int i = head[u]; i + 1; i = edge[i].nxt){
  96.         int v = edge[i].v;
  97.         if(!dfn[v]){
  98.             Tarjan(v);
  99.             low[u] = min(low[u], low[v]);
  100.         }else if(instack[v]) low[u] = min(low[u], low[v]);
  101.     }
  102.     if(low[u] == dfn[u]){
  103.         ++scc_cnt;
  104.         int top;
  105.         do{
  106.             top = sta.top();
  107.             sta.pop();
  108.             instack[top] = false;
  109.             belong[top] = scc_cnt;
  110.             sccval[scc_cnt] += val[top];
  111.             //cerr <<"scc_cnt = "<< scc_cnt <<", top = "<< top <<", val[top] = "<< val[top] <<", sccval[scc_cnt] = "<< sccval[scc_cnt] << endl;
  112.         }while(top != u && !sta.empty());
  113.     }
  114. }
  116. void SPFA(int src){
  117.     queue <int> que;
  118.     que.push(src);
  119.     vis[src] = true;
  120.     dis[src] = sccval[src];
  121.     while(!que.empty()){
  122.         int u = que.front();
  123.         que.pop();
  124.         vis[u] = false;
  125.         for(int i = shead[u]; i + 1; i = sedge[i].nxt){
  126.             int v = sedge[i].v;
  127.             dis[v] = max(dis[v], dis[u] + sccval[v]);
  128.             if(!vis[v]) que.push(v), vis[v] = true;
  129.         }
  130.     }
  131. }
  133. void solve(){
  135.     for(int i = 0; i < n * m; i++)
  136.         if(!dfn[i]) Tarjan(i);
  138.     //cerr <<"scc_cnt = "<< scc_cnt << endl;
  139.     //for(int i = 0; i < n * m; i++)
  140.         //cerr <<"i = "<< i <<", belong[i] = "<< belong[i] <<", sccval[belong[i]] = "<< sccval[belong[i]] << endl;
  142.     for(int u = 0; u < n * m; u++)
  143.         for(int i = head[u]; i + 1; i = edge[i].nxt){
  144.             int v = edge[i].v;
  145.             if(belong[u] != belong[v]) addEdge(shead, sedge, belong[u], belong[v], scnt);
  146.         }
  148.     SPFA(belong[0]);
  150.     int ans = 0;
  151.     for(int i = 1; i <= scc_cnt; i++)
  152.         ans = max(ans, dis[i]);
  154.     printf("%d\n", ans);
  155. }
  157. int main(){
  158.     int t;
  159.     scanf("%d", &t);
  160.     while(t--){
  162.         init();
  163.         Input();
  164.         solve();
  166.     }
  167.     return 0;
  168. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注