P6134 [JSOI2015]最小表示

是个汉子 · 2020-10-28 00:08:05 · 题解

洛谷传送门

Solution

显然可以看出来的一点是：一条边 u\rightarrow v 如果删除，仍然能从 u 走到 v

那我们可以贪心的去考虑，对于每一对点对 u,v ，保留其最长的路径，其余的都删了

具体实现可以对原图进行一遍拓扑排序，在过程中记录入队的时间。

对每个点，因为最长路径上一定包含先访问的点，所以把和它直接连接的点按照时间戳排序，维护连通性，统计答案即可。

但是，如果正序去考虑，我们是不知道点之间联通性的，所以倒序处理。

此时时间复杂度是 O(nm) 是通不过本题的，需要用 bitset 维护联通性来优化复杂度。

现在复杂度是 O(\frac {nm}{32})

小细节：因为无环，所以删一条边和别的边没有关联，也就是相互独立

Code

#include<cmath>
#include<queue>
#include<bitset>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>

using namespace std;
const int N=30010;
struct edge{
    int to,nxt;
}e[N*10];
int head[N],cnt,n,m;
int vis[N],in[N],ind[N];
bitset<N>rd[N];//联通性
int topu[N];

inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
    while(isdigit(ch)){x=x*10+(ch^48);ch=getchar();}
    return x*f;
}

inline void add(int u,int v){
    e[++cnt].to=v;
    e[cnt].nxt=head[u];
    head[u]=cnt;
}

inline bool cmp(const int &a,const int &b){
    return vis[a]<vis[b];
}

inline void topsort(){
    queue<int> q;
    for(int i=1;i<=n;i++)
        if(ind[i]==0) q.push(i);
    int tim=0;
    while(!q.empty()){
        int u=q.front();q.pop();
        in[++tim]=u;
        vis[u]=tim;
        for(int i=head[u];i;i=e[i].nxt){
            int v=e[i].to;
            ind[v]--;
            if(ind[v]==0) q.push(v);
        }
    }
    int ans=0;
    for(int i=n;i>=1;i--){
        int x=in[i],tot=0;
        rd[x][x]=1;
        for(int j=head[x];j;j=e[j].nxt)
            topu[++tot]=e[j].to;
        sort(topu+1,topu+tot+1,cmp);
        for(int j=1;j<=tot;j++){
            if(rd[x][topu[j]]) ans++;
            else rd[x]|=rd[topu[j]];
        }
    }
    printf("%d\n",ans);
}

int main(){
    n=read();m=read();
    for(int i=1;i<=m;i++){
        int u=read(),v=read();
        add(u,v);
        ind[v]++;
    }
    topsort();
    return 0;
}