題意

給出一張DAG,要求刪除盡量多的邊使得連通性不變.(即:若刪邊前u到v有路徑,則刪邊后仍有路徑).點(diǎn)數(shù)30000,邊數(shù)100000.

分析

如果從u到v有(u,v)這條邊,且從u到v只有這一條路徑,那么這條邊必須保留.否則這條邊一定可以刪除.因?yàn)槿绻胁恢挂粭l路徑從u到v,必然存在點(diǎn)x(x!=u,x!=v)使得u可到達(dá)x,x可到達(dá)v.而刪邊后必然也滿足u可到達(dá)x,x可到達(dá)v,所以直接刪掉(u,v)這條邊就可以了.
剛才的分析已經(jīng)給出了一個(gè)判定方法.既然如果有不止一條路徑從u到v,必然存在點(diǎn)x(x!=u,x!=v)使得u可到達(dá)x,x可到達(dá)v,那么我們對每條邊(u,v),枚舉是否存在這樣的x即可.這需要我們求出每個(gè)點(diǎn)能到達(dá)的點(diǎn)的集合,以及能到達(dá)這個(gè)點(diǎn)的集合.大力壓位一波就好了.因?yàn)槭荄AG所以這個(gè)集合可以遞推.復(fù)雜度O(nm/32).
其實(shí)這題是看內(nèi)存猜算法系列,榜上清一色的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; }

轉(zhuǎn)載于:https://www.cnblogs.com/liu-runda/p/6921499.html

總結(jié)

以上是生活随笔為你收集整理的bzoj4484[JSOI2015]最小表示的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。