自动搬运

查看原文

来自洛谷，原作者为

	伊地知虹夏 下北泽大天使

搬运于2025-08-24 22:47:57，当前版本为作者最后更新于2023-06-05 10:46:50，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

称 $f(x)$ 为 $x$ 在 $G'$ 中对应的边。

引理1

对于 $G$ 中 $x \rightarrow y$ 这条边，由于边权大于 $0$，那么 $G$ 中若存在 $x \rightarrow u \rightarrow y$，$x \rightarrow y$ 就不可能成为最长路 $S$ 中的边。

引理2

对于 $G$ 中 $x \rightarrow u,y \rightarrow u$ ，那么在 $G'$ 中，$f(x),f(y)$ 的终点是相同的，且它们能到达的点集也相同。

推论

如果存在 $x\rightarrow u,y \rightarrow u,x \rightarrow v$ 且 $y$ 不可达 $v$ 显然无解，由引理 $2$ 可证。

做法

由引理 1，对于这种边的寻找，我们可以先求出每个点能到达哪些点。设 $g(x)$ 表示 $x$ 能到达的点集，而显然有 $f(x) = \large{\cup_{\exists x \rightarrow y}} \small{g(y)}$，容易发现这个转移方程的递推顺序为 $G$ 的逆拓扑序。所以我们可以先求出 $G$ 的逆拓扑序，然后按照其递推。如果未更新 $x \rightarrow y$ 且 $y \in g(x)$，那么 $f(x)\rightarrow f(y)$ 无必要存在于 $G'$ 中，将其删去。这一步的复杂度为 $\Theta(m \frac{n}{w})$。

将每个点能到达的点集用并查集维护，如果出现 $|f(x)| \ne |f($可达 $f(x))|$，即出现 $x\rightarrow u,y \rightarrow u,x \rightarrow v$ 且 $y$ 不可达 $v$，那么输出 -1。

最终将每个点集看作一个点，枚举 1..n 将 $i$ 所属的点集的代表元向 $f(i)$ 所属的点集的代表元连一条以 $w_i$ 为权的边，若 $f(i)$ 为空集，将 $i$ 所属的点集的代表元向虚点连一条以 $w_i$ 为权的边。

至此，此题就完成了，复杂度为 $\Theta(m \frac{n}{w} + n + m)$。

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 2e4 + 5;
int n, m;
int in[N];
int col[N], cnt;
int top[N], tt;
int fa[N], siz[N],vis[N];
bitset<N> g[N];
vector<int> G[N], able[N];
void init()
{
    for (int i = 1; i <= n; i++)
        fa[i] = i, siz[i] = 1;
    return;
}
int find(int x)
{
    if (fa[x] == x)
        return x;
    return fa[x] = find(fa[x]);
}
void merge(int x, int y)
{
    int fx = find(x), fy = find(y);
    if (fx != fy)
        fa[fx] = fy, siz[fy] += siz[fx];
    return;
}
void Topo_Sort()
{ // 为了求出Topo序
    queue<int> q;
    for (int i = 1; i <= n; i++)
        if (!in[i])
            q.push(i);
    while (q.size())
    {
        int u = q.front();
        q.pop();
        top[++tt] = u;
        for (auto y : G[u])
            if (--in[y] == 0)
                q.push(y);
    }
    return;
}
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int a, b;
        cin >> a >> b;
        G[a].push_back(b);
        in[b]++;
    }
    Topo_Sort();
    init();
    for (int i = n; i; i--)
    {
        int x = top[i];
        for (int j = 0; j < G[x].size(); j++)
        {
            int y = G[x][j];
            vis[j] = g[x][y];
            g[x] |= g[y];
        }
        g[x].reset();
        g[x][x] = 1;
        for (int j = G[x].size() - 1; j >= 0; j--)
        {
            int y = G[x][j];
            vis[j] |= g[x][y];
            g[x] |= g[y];
            if (!vis[j])
                able[x].push_back(y);
        }
        for (auto y : able[x])
            merge(able[x][0], y);
    }
    for (int i = 1; i <= n; i++)
    {
        if (find(i) == i)
            col[i] = ++cnt;
        if (able[i].size() && siz[find(able[i][0])] != able[i].size())
        {
            cout << -1;
            return 0;
        }
    }
    cout << (++cnt) << '\n';
    for (int i = 1; i <= n; i++)
        if (able[i].size())
            printf("%d %d %d\n", col[find(i)], col[find(able[i][0])], i);
        else
            printf("%d %d %d\n", col[find(i)], cnt, i);
    return 0;
}