[BZOJ1791][IOI2008]Island 岛屿

题意

给定一个n个点n条边的有向图，其中每个点都只有一条出边，然后添上每条边的反向边（也就是原地变成无向图），问在每个点都只经过一次的情况下，最长的路程是多少。

分析

首先分析一下n个点n条边的图会是什么样的。去掉一条边比较好想，要么一棵树，要么若干棵个环+一棵树。那么把这条边加上去，这条边显然只能让一棵树产生一个环，或者是连接一棵树和一个环，不可能连接两个环（因为每个点只有一条出边，组成环必然用完了每个点的出边）。总的是来说，这一张图就是：若干个连通分量，并且每个联通分量里面只能是一个中心环+若干棵外向树。

我们对于每个联通分量单独考虑，然后再把每个联通分量里面的最长路径加起来就是答案了（因为题目说岛之间是坐船，不算在行走路程里面）。

现在我们的问题是：对于一个环+若干个外向树，如何求出最远距离？

显然最远距离不可能是在环上，因为可以向外向树延伸，让路径变得更长。所以答案仅有下面两种可能性：

  • 两端在某一棵外向树上
  • 一端在某一棵外向树上，然后走了环的一部分，最终到达另外一棵外向树

第一种只要对于每一棵外向树计算出最远距离就好了。我们来考虑一下如何计算第二种的答案。

首先，对于在外向树的那两部分，肯定是走从环到这棵外向树最远的点，这个可以跟着第一种情况一起算出来（如果是写两次BFS的话，第一次BFS的结果就是这个的结果，第二次的结果就是第一种情况的结果）。

然后我们按顺序给环上的节点标号，再计算下环上每个点到环的基准点的距离和s[i]。记整个环的路径和是sum，那么环上点i到j的距离要么是s[i]-s[j]要么是sum-(s[i]-s[j])。如果再假设每环上的个点到它的外向树的最远距离是d[i]，那么答案就是：

max {
    s[i] - s[j] + d[i] + d[j],
    sum - (s[i] - s[j]) + d[i] + d[j]
}

变形一下

max {
    [(s[i] + d[i])]       - (s[j] - d[j]),
    [sum - (s[i] - d[i])] + (s[j] + d[j])
}

注意到中括号里面的数值，对于当前的i来说是不变的，要取到最大，那么：对于上面那个，记录1i中s[j]-d[j]最小的；对于下面那个，记录1i中s[j]+d[j]最大的。然后这题就这么解决了。

网上另外一种做法是：把环拉成2*n的链，然后限制每次头尾之间的距离不能超过n，用单调队列来维护。比较麻烦，但也可做。

实现

实现的时候，求环其实是一件很蛋疼的事情，直觉上告诉我们，用DFS乱搞一下就可以，怕爆栈就写模拟栈或者BFS。但是实际上，模拟栈很难写，而BFS又找不出环。用Tarjan的话又有点小题大做。

后来请教了xietutu大神以后才知道，因为这题保证每一个点都只有一条出边，所以只要跟着读入的顺序走，然后碰到访问过的点，就出现了环了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112

#include <stack>
#include <cstdio>
#include <cstring>
#include <algorithm>

const int MAXN = 1000001;
struct Edge
{
  int v, w;
  Edge *next;
} g[MAXN*2], *header[MAXN];
bool vis1[MAXN], vis2[MAXN];
int C, n, ncir, color[MAXN], map[MAXN], Q[MAXN], road[MAXN][2];
long long d[MAXN], s[MAXN];
void AddEdge(const int x, const int y, const int w)
{
  static int LinkSize;
  Edge* const node = g+(LinkSize++);
  node->v = y;
  node->w = w;
  node->next = header[x];
  header[x] = node;
}
long long GetDiameter(const int source, const int c, const bool first, bool (&vis)[MAXN])
{
  static long long dist[MAXN];
  int head = 0, tail = -1, k = -1;
  long long ans = 0;
  Q[++tail] = source, dist[tail] = 0, color[source] = c, vis[source] = true;
  while (head <= tail)
  {
    if (dist[head] > ans)
    {
      ans = dist[head];
      k = Q[head];
    }
    const int u = Q[head];
    for (Edge *e = header[u]; e; e = e->next)
      if (color[e->v] != -1 && !vis[e->v])
      {
        Q[++tail] = e->v, dist[tail] = dist[head] + e->w;
        color[e->v] = c, vis[e->v] = true;
      }
    ++head;
  }
  if (first) d[source] = ans;
  return first ? k : ans;
}
void GetCircle(const int source)
{
  static int pre[MAXN];
  static long long w[MAXN];
  static bool vis[MAXN];
  vis[source] = true;
  for (int u = source, v; true; u = v)
  {
    v = road[u][0];
    if (vis[v])
    {
      map[0] = v, s[1] = road[u][1], color[v] = -1;
      for (int i = u; i != v; i = pre[i])
        map[++ncir] = i, s[ncir+1] = s[ncir] + w[i], color[i] = -1;
      ++ncir;
      return;
    }
    pre[v] = u;
    w[v] = road[u][1];
    vis[v] = true;
  }
}

int main()
{
  scanf("%d", &n);
  for (int i = 1, x, y; i <= n; ++i)
  {
    scanf("%d%d", &x ,&y);
    road[i][0] = x, road[i][1] = y;
    AddEdge(i, x, y);
    AddEdge(x, i, y);
  }
  long long ans = 0;
  for (int i = 1; i <= n; ++i)
    if (!color[i])
    {
      ncir = 0;
      GetCircle(i);
      long long m = 0;
      for (int i = 0; i < ncir; ++i)
      {
        color[map[i]] = 0;
        const int v = GetDiameter(map[i], ++C, true, vis1);
        if (v != -1)
        {
          const long long dist = GetDiameter(v, C, false, vis2);
          m = std::max(m, dist);
        }
        color[map[i]] = -1;
      }
      long long tmp1 = s[0]-d[map[0]], tmp2 = s[0]+d[map[0]];
      for (int i = 1; i < ncir; ++i)
      {
        m = std::max(m, s[i]+d[map[i]] - tmp1);
        m = std::max(m, s[ncir] - (s[i]-d[map[i]]) + tmp2);
        tmp1 = std::min(tmp1, s[i]-d[map[i]]);
        tmp2 = std::max(tmp2, s[i]+d[map[i]]);
      }
      ans += m;
    }

  printf("%lld", ans);
}

Comments