20221018题解

发表于 2022-10-19 阅读次数：

T1 road

思路分析

首先可以观察边权的表达式： \(c + \lfloor\frac{d}{t + 1}\rfloor\) 。

由于题目说了可以等待，我们可以发现如果等待 1 秒带来的收益（即 \(\lfloor\frac{d}{t + 1}\rfloor\) 的减少量）大于 1 ，那么一定要等；如果获得 1 的收益需要等待不止 1 秒，那么一定不需要等。尝试去掉下取整，用数学语言描述两个条件分别如下：

\[ \begin{gather*} \frac{d}{t + 1} - \frac{d}{t + 2} > 1 \\ \frac{d}{t + 1} - \frac{d}{t + 2} < 1 \end{gather*} \]

解得两个不等式的解如下：

\[ \begin{gather*} t < \frac{\sqrt{4d + 1} - 3}{2} \\ t > \frac{\sqrt{4d + 1} - 3}{2} \end{gather*} \]

当第一条成立的时候，立即就走，否则等到时刻 \(\lfloor\frac{\sqrt{4d + 1} - 3}{2}\rfloor + 1\) 再走。这样比标程常数小的多（标程尝试了 4 种边权）。

当然，你如果不放心，直接在 \(\sqrt d\) 附近多试几个数就好了。

剩下的就是堆优化 \(Dijkstra\) 。

AC 代码

code

#include <bits/stdc++.h>
using namespace std;

#define NAME "road"

const int maxn = 1e5 + 5;

struct edge {
    int v;
    long long c, d;
    edge(int _v, long long _c, long long _d) { v = _v, c = _c, d = _d; }
};

vector<edge> graph[maxn];
int n, m;
bool vis[maxn];
priority_queue<pair<long long, int>, vector<pair<long long, int> >, greater<pair<long long, int> > > pq;

int main() {
    freopen(NAME ".in", "r", stdin);
    freopen(NAME ".out", "w", stdout);
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= m; i++) {
        static int u, v;
        static long long c, d;
        scanf("%d %d %lld %lld", &u, &v, &c, &d);
        graph[u].emplace_back(v, c, d);
        graph[v].emplace_back(u, c, d);
    }
    pq.emplace(0LL, 1);
    while (!pq.empty()) {
        pair<long long, int> now = pq.top();
        pq.pop();
        if (vis[now.second]) continue;
        vis[now.second] = true;
        if (now.second == n) {
            printf("%lld\n", now.first);
            return 0;
        }
        for (edge e : graph[now.second]) {
            if (vis[e.v]) continue;
            long long sqt = sqrt((e.d << 2) + 1);
            if (now.first > (sqt - 3) >> 1) pq.emplace(now.first + e.c + e.d / (now.first + 1), e.v);
            else {
                // pq.emplace(((sqt - 3) >> 1) + e.c + e.d / (((sqt - 3) >> 1) + 1), e.v);
                pq.emplace((((sqt - 3) >> 1) + 1) + e.c + e.d / (((sqt - 3) >> 1) + 2), e.v);
            }
        }
    }
    printf("-1\n");
    return 0;
}

T2

思路分析

对于边 \((u, v)\) ， \(u, v\) 在同一个强连通分量的充要条件是 \(v\) 能到 \(u\) 。此时如果 \((u, v)\) 是 \(u\) 到 \(v\) 的必经边，那么翻转后强连通分量个数会变多。如果不是必经边，则强连通分量不会变。

而如果 \(v\) 本来就不能到 \(u\) ，那么翻转后 \(v\) 就能到 \(u\) 了。此时如果 \(u\) 还能到 \(v\) ，即 \((u, v)\) 不是必经边，那么强连通分量就变少了。如果 \((u, v)\) 是必经边，即翻转后 \(u\) 不能到 \(v\) 了，强连通分量不会变。

所以只需要考虑两个问题：

两点之间的可达性
一条边是否为必经边

第一个问题以每个点为起点搜一次就行了。时间复杂度 \(O(NM)\) 。

第二个问题看这张图：

由图上可以看出， \((1, 4)\) 并不是从 1 到 4 的必经边，因为从 1 到 4 有两种方法可达。在对从 1 开始的可达性搜索中，我们考虑在记录可达性的时候顺便记录是从 1 的哪一条出边开始搜的时候搜到的。那么，我们先按照某一个顺序选择 1 的出边，把数据记录在一个数组中。然后按照倒序再次进行搜索，记录在另一个数组中。因为 1 到 4 有不止一种方式可达，一个是 \(1 \rightarrow 4\) ，另一种是 \(1 \rightarrow 2 \rightarrow 3 \rightarrow 4\) ，那么 4 两次搜索记录的出边来源必然是不同的，一次记录了 \((1, 2)\) ，一次记录了 \((1, 4)\) 。反之如果 \(1\) 到 \(4\) 只有一种路径，那么两次搜索结果是一样的。这样就在 \(O(NM)\) 的时间解决了。

AC 代码

code

#include <bits/stdc++.h>
using namespace std;

#define NAME "turn"

const int maxn = 1e3 + 5, maxm = 2e5 + 5;

int n, m;
int uu[maxm], vv[maxm];
vector<int> graph[maxn];
int vis[maxn][maxn], vis_reverse[maxn][maxn];

void dfs(int u, int from, int *a) {
    if (a[u]) return;
    a[u] = from;
    for (int v : graph[u]) dfs(v, from, a);
}

int main() {
    freopen(NAME ".in", "r", stdin);
    freopen(NAME ".out", "w", stdout);
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= m; i++) {
        scanf("%d %d", uu + i, vv + i);
        graph[uu[i]].emplace_back(vv[i]);
    }
    for (int i = 1; i <= n; i++) {
        vis[i][i] = vis_reverse[i][i] = i;
        for (int u : graph[i]) dfs(u, u, vis[i]);
        reverse(graph[i].begin(), graph[i].end());
        for (int u : graph[i]) dfs(u, u, vis_reverse[i]);
    }
    for (int i = 1; i <= m; i++) {
        if ((vis[uu[i]][vv[i]] != vis_reverse[uu[i]][vv[i]]) ^ (vis[vv[i]][uu[i]] > 0)) printf("diff\n");
        else printf("same\n");
    }
    return 0;
}