bzoj4484[JSOI2015]最小表示

题意

给出一张DAG,要求删除尽量多的边使得连通性不变.(即:若删边前u到v有路径,则删边后仍有路径).点数30000,边数100000.

分析

如果从u到v有(u,v)这条边,且从u到v只有这一条路径,那么这条边必须保留.否则这条边一定可以删除.因为如果有不止一条路径从u到v,必然存在点x(x!=u,x!=v)使得u可到达x,x可到达v.而删边后必然也满足u可到达x,x可到达v,所以直接删掉(u,v)这条边就可以了.
刚才的分析已经给出了一个判定方法.既然如果有不止一条路径从u到v,必然存在点x(x!=u,x!=v)使得u可到达x,x可到达v,那么我们对每条边(u,v),枚举是否存在这样的x即可.这需要我们求出每个点能到达的点的集合,以及能到达这个点的集合.大力压位一波就好了.因为是DAG所以这个集合可以递推.复杂度O(nm/32).
其实这题是看内存猜算法系列,榜上清一色的120多兆,不是压位还能是啥
我是200多兆

#include<cstdio> const int mod=1000000007; const int maxn=30005,maxm=200005; struct edge{int to,next; }lst[maxm],lst2[maxm];int len=1,first[maxn],len2=1,first2[maxn]; void addedge(int a,int b){lst[len].to=b;lst[len].next=first[a];first[a]=len++; } void addedge2(int a,int b){lst2[len2].to=b;lst2[len2].next=first2[a];first2[a]=len2++; } int sz; int reach[maxn][maxn/32+2],from[maxn][maxn/32+2]; int getbit(int u,int x){return (reach[u][x/32]>>(x&31))&1; } void revbit(int u,int x){reach[u][x/32]^=(1<<(x&31)); } void revbit2(int u,int x){from[u][x/32]^=(1<<(x&31)); } bool vis[maxn]; void dfs(int x){if(vis[x])return;vis[x]=true;for(int pt=first[x];pt;pt=lst[pt].next){dfs(lst[pt].to);for(int i=0;i<sz;++i)reach[x][i]|=reach[lst[pt].to][i];}revbit(x,x); } void dfs2(int x){if(vis[x])return;vis[x]=true;for(int pt=first2[x];pt;pt=lst2[pt].next){dfs2(lst2[pt].to);for(int i=0;i<sz;++i)from[x][i]|=from[lst2[pt].to][i];}revbit2(x,x); } int main(){int n,m;scanf("%d%d",&n,&m);sz=(n+31)/32+1;for(int i=1,a,b;i<=m;++i){scanf("%d%d",&a,&b);addedge(a,b);addedge2(b,a);}for(int i=1;i<=n;++i)if(!vis[i])dfs(i);for(int i=1;i<=n;++i)vis[i]=0;for(int i=1;i<=n;++i)if(!vis[i])dfs2(i);for(int i=1;i<=n;++i)revbit(i,i),revbit2(i,i);int ans=0;for(int i=1;i<=n;++i){for(int pt=first[i];pt;pt=lst[pt].next){int y=lst[pt].to;for(int j=0;j<sz;++j){if(from[y][j]&reach[i][j]){ans++;break;}}}}printf("%d\n",ans);return 0; }

转载于:https://www.cnblogs.com/liu-runda/p/6921499.html

总结

以上是生活随笔为你收集整理的bzoj4484[JSOI2015]最小表示的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。