BZOJ：3832: [Poi2014]Rally

题意：

给出$DAG$，询问删掉哪个点之后最长路径最短

思路：

我们令$f[x]$表示从最远的点到达它的距离，$g[x]$表示它能够到达最远的点的距离

那么对于$(x -> y)$一条边来说，它所在的最长路径就是 $f[x] + 1 + g[y]$

我们按照拓扑序依次删点

我们发现此时删去一个点，那么可能存在的最长的路径是

和它同一层的点所在的路径，以及它前一层的点所在的路径，以及它后一层的点所在的路径

因为它只会影响到它前一层的点和后一层的点

那么我们删去它所有入边的贡献，以及它本身的$g[x]$的贡献

再更新答案后

我们加入它出边的贡献，以及它本身的$f[x]$的贡献

  1 #include <bits/stdc++.h>
  2 using namespace std;
  3 
  4 #define N 500010
  5 int n, m;
  6 vector <int> G[2][N];
  7 int f[N], g[N];
  8 
  9 namespace SEG
 10 {
 11     int cnt[N << 3], Max[N << 3];
 12     void build(int id, int l, int r)
 13     {
 14         cnt[id] = Max[id] = 0;
 15         if (l == r)
 16             return;
 17         int mid = (l + r) >> 1;
 18         build(id << 1, l, mid);
 19         build(id << 1 | 1, mid + 1, r);
 20     }
 21     void update(int id, int l, int r, int pos, int v)
 22     {
 23         if (pos == 0) return;
 24         if (l == r)
 25         {
 26             cnt[id] += v;
 27             if (cnt[id] > 0) Max[id] = pos;
 28             else Max[id] = 0; 
 29             return;
 30         }
 31         int mid = (l + r) >> 1;
 32         if (pos <= mid) update(id << 1, l, mid, pos, v);
 33         else update(id << 1 | 1, mid + 1, r, pos, v);
 34         Max[id] = max(Max[id << 1], Max[id << 1 | 1]); 
 35     }
 36 }
 37 
 38 int id[N], d[2][N];
 39 void Toposort()
 40 {
 41     id[0] = 0;
 42     memset(f, 0, sizeof f);
 43     memset(g, 0, sizeof g);
 44     queue <int> q;
 45     for (int i = 1; i <= n; ++i)
 46         if (d[0][i] == 0)
 47             q.push(i);
 48     while (!q.empty())
 49     {
 50         int u = q.front(); q.pop();
 51         id[++id[0]] = u;
 52         for (int v, it = 0, len = G[0][u].size(); it < len; ++it)
 53         {
 54             v = G[0][u][it];
 55             if (--d[0][v] == 0)
 56             {
 57                 f[v] = f[u] + 1;
 58                 q.push(v); 
 59             }
 60         }
 61     }
 62     for (int i = 1; i <= n; ++i)
 63         if (d[1][i] == 0)
 64             q.push(i);
 65     while (!q.empty())
 66     {
 67         int u = q.front(); q.pop();
 68         for (int v, it = 0, len = G[1][u].size(); it < len; ++it)
 69         {
 70             v = G[1][u][it];
 71             if (--d[1][v] == 0)
 72             {
 73                 g[v] = g[u] + 1;
 74                 q.push(v);
 75             }
 76         }
 77     }
 78 }
 79 
 80 
 81 
 82 void Run()
 83 {
 84     while (scanf("%d%d", &n, &m) != EOF)
 85     {
 86         for (int i = 1; i <= n; ++i)
 87             G[0][i].clear(), G[1][i].clear();
 88         memset(d, 0, sizeof d);
 89         SEG::build(1, 1, m); 
 90         for (int i = 1, u, v; i <= m; ++i)
 91         {
 92             scanf("%d%d", &u, &v);
 93             G[0][u].push_back(v); ++d[0][v];
 94             G[1][v].push_back(u); ++d[1][u];
 95         }
 96         Toposort();
 97         for (int i = 1; i <= n; ++i)
 98             SEG::update(1, 1, m, g[i], 1);
 99         int Min = (int)1e9, pos = -1;
100         for (int x, i = 1; i <= n; ++i)
101         {
102             x = id[i];
103             for (int v, it = 0, len = G[1][x].size(); it < len; ++it)
104             {
105                 v = G[1][x][it];
106                 SEG::update(1, 1, m, f[v] + 1 + g[x], -1);
107             }
108             SEG::update(1, 1, m, g[x], -1); 
109             int now = SEG::Max[1]; 
110             if (now < Min)
111             {
112                 Min = now;
113                 pos = x;
114             }
115             SEG::update(1, 1, m, f[x], 1);
116             for (int v, it = 0, len = G[0][x].size(); it < len; ++it)
117             {
118                 v = G[0][x][it];
119                 SEG::update(1, 1, m, f[x] + 1 + g[v], 1);
120             }
121         }
122         printf("%d %d
", pos, Min);
123     }
124 }
125 
126 int main()
127 {
128     #ifdef LOCAL
129         freopen("Test.in", "r", stdin);
130     #endif 
131 
132     Run();
133     return 0;
134 }

View Code