洛谷P6134 [JSOI2015]最小表示题解

题目链接：P6134 [JSOI2015]最小表示

题意：

对于一个 \(N\) 个点（每个点从 \(1\) 到 \(N\) 编号），\(M\) 条边的有向图，cxy 发现，如果从图中删去一些边，那么原图的连通性会发生改变；而也有一些边，删去之后图的连通性并不会发生改变。

cxy 想知道，如果想要使得原图任意两点的连通性保持不变，我们最多能删掉多少条边呢？

为了简化一下大家的工作量，这次 cxy 保证他给定的有向图一定是一个有向无环图（cxy：大家都知道对于给任意有向图的问题，最后都能转化为有向无环图上的问题，所以就干脆简化一下大家的工作）。

输入格式：

第一行包含两个正整数 \(N\) 和 \(M\)。

接下来 \(M\) 行，每行包含两个 \(1\) 到 \(N\) 之间的正整数 \(x_i\) 和 \(y_i\)，表示图中存在一条从 \(x_i\) 到 \(y_i\) 的有向边。

输入数据保证，任意两点间只会有至多一条边存在。

输出格式：

输出一行包含一个整数，表示cxy最多可以删掉的边数。

数据范围：

对于 \(100\%\) 的数据，\(1 \leq N\leq 3\times 10^4\)，\(0 \leq M\leq 10^5\)。

不难发现每对节点保留其最长的路径一定可以得到最优解。

证明：

~~感性理解的话~~，是因为保留这些边的过程最大化了边的利用价值。

考虑原图的一个拓扑序，显然它构成一棵树，且边均由子结点指向父结点

当然拓扑序不能反映原图的连通性，实际上这棵树上还有一些“返祖边”

这里“返祖边”类似于dfs树的返祖边，由某个结点指向它的某个祖先或祖先的兄弟。

如果 \(u\) 为叶子结点，显然仅留“返祖边”是最优的。

如果 \(u\) 不为叶子结点，我们首先会尝试让 \(u\) 的儿子连上 \(u\) ，然后尝试 \(u\) 的孙子...

不难发现这样一定是优的，因为连深度较大的结点只会让答案增大。

至此，我们证明了算法的正确性。\(\square\)

考虑用 \(\mathtt{bitset}\) 维护结点的连通性。

设 \(u\) 向 \(v\) 连了一条有向边。

我们用 link[u][v] 表示 \(u\) 与 \(v\) 连通
因为 \(v\) 能到达的结点 \(u\) 也能到达，因此我们可以直接 link[u] |= link[v]

时间复杂度 \(\mathcal{O}\left(\frac{n^2\log n}{32}\right)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(3e4+15))
#define M ((int)(1e5+15))

bitset<N> link[N];
int n,m,pos=1,head[N],to[N],in[N],id[N],dfn[N];
struct Edge{int u,v,next;} e[M];
void addEdge(int u,int v) { e[++pos] = {u,v,head[u]}; head[u] = pos; }
int topo()
{
    int res=0,tim=0; queue<int> q;
    for(int i=1; i<=n; i++) if(!in[i]) q.push(i);
    while(!q.empty())
    {
        int u = q.front(); q.pop();
        id[++tim] = u; dfn[u] = tim;
        for(int i=head[u]; i; i=e[i].next)
            if(!(--in[e[i].v])) q.push(e[i].v);
    }
    for(int k=n; k>=1; k--)
    {
        int u = id[k], cnt=0; link[u][u] = 1;
        for(int i=head[u]; i; i=e[i].next)
            to[++cnt] = e[i].v;
        sort(to+1, to+1+cnt, [](int a,int b) { return dfn[a] < dfn[b]; });
        for(int i=1; i<=cnt; i++)
            if(link[u][to[i]]) ++res;
            else link[u] |= link[to[i]];
    }
    return res;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> m;
    for(int i=1,u,v; i<=m; i++)
    {
        cin >> u >> v;
        addEdge(u,v); ++in[v];
    }
    cout << topo() << '\n';
    return 0;
}