P6134 [JSOI2015]最小表示

yhx's blog

给定一个有向图无环，问最多可以删去多少条边使得图的连通性不变。

首先考虑在什么情况下会被删：假设边((u,v))，那么当且仅当存在一个(w)，使得 (u) 可以到达 (w) ，且 (w) 可以到达 (v) 。

也就是说我们考虑“绕路”。

但是，我们怎么知道这个 (w) 的存在呢？——我们可以维护每一个点到其他点的连通性。

但是我们如果遍历的先后顺序有影响呢？不就统计不到了吗？

所以我们有下面这样的性质：统计一个点延伸出去的最长路，然后先访问最长路长的点。

为什么呢？——因为长的点有可能到达短的点，而短的点不可能到达长的点。

正确性显然。

然后有向图连通性明显使用 bitset 来优化，时间复杂度 (O(frac{nm}{w}))

代码：

#include<bits/stdc++.h>
using namespace std;
template <typename T>
inline void read(T &x){
	x=0;char ch=getchar();bool f=false;
	while(!isdigit(ch))	f|=ch=='-',ch=getchar();
	while(isdigit(ch))	x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	x=f?-x:x;
}
template <typename T>
inline void write(T x){
	if(x<0)	putchar('-'),x=-x;
	if(x>9)	write(x/10);
	putchar(x%10^48);
}
#define ll long long
const int N=3e4+5,M=1e5+5;
int head[N],nex[M],to[M],idx,vec[N],dist[N];
int n,m,ans;
bool vis[N];
bitset<N> s[N];
void add(int u,int v){
	nex[++idx]=head[u];
	to[idx]=v;
	head[u]=idx;
	return ;
}
bool cmp(int x,int y){return dist[x]>dist[y];}
void dfs(int x){
	if(vis[x]) return ;
	vis[x]=true;int top=0;
	for(int i=head[x];i;i=nex[i]){int y=to[i];dfs(y);dist[x]=max(dist[x],dist[y]+1);}
	for(int i=head[x];i;i=nex[i]){int y=to[i];vec[++top]=y;}
	sort(vec+1,vec+top+1,cmp);
	for(int i=1;i<=top;i++){
		if(s[x][vec[i]]) ans++;
		else s[x]|=s[vec[i]];
	}
	return ;
}
signed main(){
	read(n),read(m);
	for(int i=1;i<=m;i++){
		int u,v;
		read(u),read(v);
		add(u,v);
	}
	for(int i=1;i<=n;i++) s[i][i]=1;
	for(int i=1;i<=n;i++) if(!vis[i]) dfs(i);
	write(ans);
	return 0;
}

P6134 [JSOI2015]最小表示

相关推荐