对Tarjan的算法理解有点要求的题,之前看了一下思路,敲了一下结果没过,照着博客改动了一下但并没有搞懂,今天补上。

题意:
给你一个有向图,若干询问,询问为从 s 到 t 的最小字典序路径中,第 k 个点是哪个点。

思路:
首先询问很多,有4\times10^5个询问,直接一个一个找肯定是不行的。
但是值得注意的是,点数比较少,只有3000个,假如我们固定起点,遍历全图来获得路径,在遍历的同时,对每一个点来记录答案。理想复杂度为O(N^2),时间上满足条件。

一个问题是如何保证字典序最小,emmmm
用vector记录整张图,对于每个点的边进行排序,因为每个点访问一次,解决之。

这题还有一个合理的大坑,如果在遍历的时候,在之前已经出现了一个环,那么之后的所有点就都不会被访问。
当然你不能在找到一个环后,后面的点就不再遍历,这样会使最小字典树发生变化,会导致错误答案。
好题啊。

以上。

#include <bits/stdc++.h>

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(ary, num) memset((ary), (num), sizeof(ary))

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

const int maxn = 3e3 + 5;
const int maxq = 4e5 + 5;

struct Item {
    int u, v, q, id;
    bool operator<(const Item& item) const { return u < item.u; }
} items[maxq];

int dfn[maxn], low[maxn], vis[maxn], vtm;
int path[maxn], ans[maxq];
vector<int> G[maxn];
vector<Item> qary[maxn];

void tarjan(int u, int dep, bool cant)
{
    path[dep] = u;
    low[u] = dfn[u] = ++vtm;
    vis[u] = 1;
    int sz = qary[u].size();
    if (!cant)
        each(i, sz)
        {
            Item& item = qary[u][i];
            if (item.q <= dep)
                ans[item.id] = path[item.q];
        }
    sz = G[u].size();
    each(i, sz)
    {
        int v = G[u][i];
        if (!vis[v]) {
            tarjan(v, dep + 1, cant | (low[u] < dfn[u]));
            low[u] = min(low[u], low[v]);
            cant |= (low[v] < dfn[v]);
        } else if (vis[v] == 1)
            low[u] = min(low[u], dfn[v]);
    }
    vis[u] = 2;
}

int main()
{
    int n, m, q, u, v;
    scanf("%d %d %d", &n, &m, &q);
    each(i, m)
    {
        scanf("%d %d", &u, &v);
        G[u].push_back(v);
    }
    range(i, 1, n) sort(G[i].begin(), G[i].end());
    each(i, q)
    {
        Item& item = items[i];
        scanf("%d %d %d", &item.u, &item.v, &item.q);
        item.id = i;
    }
    sort(items, items + q);
    fill(ans, -1);
    each(i, q)
    {
        Item& item = items[i];
        qary[item.v].push_back(item);
        if (i == q - 1 || item.u != items[i + 1].u) {
            vtm = 0, fill(vis, 0);
            tarjan(item.u, 1, false);
            range(j, 1, n) qary[j].clear();
        }
    }
    each(i, q) printf("%d\n", ans[i]);
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注

Related Posts

强联通分量

HDU 6165 FFF at Valentine

好烦,感觉自己的图论知识都有了,但是一旦写起来还是非常欠缺…… 什么时 Read more…

强联通分量

Kosaraju算法入门 ( 附 POJ 2186

算法详解 花了一点小时间入门了 kosaraju 算法。 记得之前在一 Read more…

强联通分量

HDU 6073 Matching In Multiplication

今天多校的第一锅…… 这套题真是神奇,明明都是Claris出的,涉及图 Read more…