题目：https://www.lydsy.com/JudgeOnline/problem.php?id=4484
每个点上存一下它到每个点的连通性。用 bitset 的话空间就是 \( \frac{n^2}{8} \) 左右。
按拓扑序从大到小枚举每个点。对于每个点判断它的哪些出边能删。然后就不太会了。
其实它的出边也不是都是等价的。连向 “拓扑序较小的点” 的出边价值更高。因为能删边的情况是 u->x->v && u->v 。
所以按指向的点拓扑序递增的顺序枚举出边，用 bitset 看看加上这条边对于连通性有无影响即可。
#include<cstdio> #include<cstring> #include<algorithm> #include<bitset> #include<queue> using namespace std; int rdn() { int ret=0;bool fx=1;char ch=getchar(); while(ch>‘9‘||ch<‘0‘){if(ch==‘-‘)fx=0;ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘)ret=ret*10+ch-‘0‘,ch=getchar(); return fx?ret:-ret; } const int N=3e4+5,M=1e5+5; int n,m,hd[N],xnt,to[M],nxt[M],dg[N],tot,a[N],dfn[N],tp[N]; bitset<N> dp[N],tmp; queue<int> q; bool cmp(int u,int v){return dfn[u]<dfn[v];} void add(int x,int y){to[++xnt]=y;nxt[xnt]=hd[x];hd[x]=xnt;dg[y]++;} int main() { n=rdn();m=rdn(); for(int i=1,u,v;i<=m;i++) u=rdn(),v=rdn(),add(u,v); for(int i=1;i<=n;i++)if(!dg[i])q.push(i); while(q.size()) { int k=q.front(); q.pop(); dfn[k]=++tot; a[tot]=k; for(int i=hd[k],v;i;i=nxt[i]) if(--dg[v=to[i]]==0)q.push(v); } int ans=0; for(int i=n;i;i--) { int cr=a[i],p=0; for(int j=hd[cr];j;j=nxt[j]) tp[++p]=to[j]; sort(tp+1,tp+p+1,cmp); for(int j=1;j<=p;j++) { int v=tp[j]; if((dp[cr]|dp[v])==dp[cr])ans++; else dp[cr]|=dp[v]; } dp[cr][cr]=1;// } printf("%d\n",ans); return 0; }
bzoj 4484 [Jsoi2015]最小表示——bitset
原文：https://www.cnblogs.com/Narh/p/10386068.html