93分求助
查看原帖
93分求助
128591
Refined_heart楼主2021/9/23 13:07

rt,第十二个点的答案在小数点第五位偏小,答案似乎有很多个孤立点的样子,不知道为什么会算错

#include<bits/stdc++.h>//smaller
using namespace std;
const int N=2e5+10;
int head[N],Head[N],tto,tot,n,m;
struct E {
	int nxt,to;
} e[N<<1],edge[N<<1];
typedef long double db;
inline void link(int x,int y,int w=0) {
	if(w) {
		edge[++tto]=(E) {
			Head[x],y
		};
		Head[x]=tto;
		return;
	}
	e[++tot]=(E) {
		head[x],y
	};
	head[x]=tot;
}
int low[N],dfn[N],st[N],top,vis[N],tg[N];
int dfstime,inst[N],col[N],node,siz[N];
inline int Min(int x,int y) {
	return x<y?x:y;
}
void tarjan(int x) {
	low[x]=dfn[x]=++dfstime;
	st[++top]=x;
	inst[x]=1;
	for(int i=head[x]; i; i=e[i].nxt) {
		int j=e[i].to;
		if(!dfn[j]) {
			tarjan(j);
			low[x]=Min(low[x],low[j]);
		} else if(inst[j])low[x]=Min(low[x],dfn[j]);
	}
	if(dfn[x]==low[x]) {
		++node;
		col[node]=node;
		int y=-1;
		while(y=st[top--]) {
			col[y]=node;
			siz[node]++;
			inst[y]=0;
			if(x==y)return;
		}
	}
}
struct EE {
	int u,v;
} edges[N];
int cnt_eg,in[N],V[N];
map<int,map<int,int> >mp;
int main() {
	freopen("in.txt","r",stdin);
	freopen("My.out","w",stdout);
	scanf("%d%d",&n,&m);
	node=n;
	for(int i=1; i<=node; ++i)siz[i]=1;
	for(int i=1; i<=m; ++i) {
		int u,v;
		scanf("%d%d",&u,&v);
		swap(u,v);
		link(v,u);
		edges[++cnt_eg]=(EE) {
			v,u
		};
	}
	for(int i=1; i<=n; ++i)if(!dfn[i])top=0,tarjan(i);
	for(int i=1; i<=cnt_eg; ++i) {
		int u=edges[i].u;
		int v=edges[i].v;
		u=col[u];
		v=col[v];
		tg[u]=1;
		tg[v]=1;
		if(u==v)continue;
		if(mp[u][v])continue;
		mp[u][v]=1;
		vis[u]=1;
		vis[v]=1;
		link(u,v,1);
		in[v]++;
	}
	int cnt=0;
	int Fg=-1;
	
	for(int i=n+1; i<=node; ++i) {
		if(!in[i])cnt++;
		if(in[i]||siz[i]>1)continue;
		if(Fg==-1) {
			int fg=1;
			for(int g=Head[i]; g; g=edge[g].nxt) {
				int v=edge[g].to;
				if(in[v]<=1) {
					fg=0;
					break;
				}
			}
			if(!Head[i])fg=1;
			if(fg) {
				Fg=1;
				cnt--;
			}
		}
	}
	printf("%.6lf\n",(double)(n-cnt)/n);
	return 0;
}
2021/9/23 13:07
加载中...