The solution for C.

伊地知虹夏 · 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;
}