救救孩子吧!80分求救!!!
查看原帖
救救孩子吧!80分求救!!!
182101
逆天峰王者楼主2020/6/2 22:00
//不等,不问,不犹豫,不回头.
#include<bits/stdc++.h>
#define ls p<<1
#define db double
#define rs p<<1|1
#define RE register
#define P 999911659
#define ll long long
#define INF 1000000000
#define get(x) x=read()
#define PLI pair<ll,int>
#define PII pair<int,int>
#define pb(x) push_back(x)
#define ull unsigned long long
#define put(x) printf("%d\n",x)
#define putl(x) printf("%lld\n",x)
#define rep(x,y,z) for(RE int x=y;x<=z;++x)
#define fep(x,y,z) for(RE int x=y;x>=z;--x)
#define go(x) for(RE int i=link[x],y=a[i].y;i;y=a[i=a[i].next].y)
using namespace std;
const int N=1e4+10,M=1e6+10;
int n,m,link1[N],link2[N],tot,du[N],s,t,vis[N],vis2[N];
int dfn[N],low[N],num,q[N],top,belong[N],o,pos[N];
db c[105][105],f[N];
struct edge{int y,next;}a[M<<1];
vector<int>v[N];

inline int read()
{
	int x=0,ff=1;
	char ch=getchar();
	while(!isdigit(ch)) {if(ch=='-') ff=-1;ch=getchar();}
	while(isdigit(ch)) {x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return x*ff;
}

inline void add(int *link,int x,int y)
{
	a[++tot].y=y;a[tot].next=link[x];link[x]=tot;
}

inline bool bfs()
{
	queue<int>q;q.push(t);
	vis[t]=1;
	while(!q.empty())
	{
		int x=q.front();q.pop();
		for(RE int i=link2[x];i;i=a[i].next)
		{
			int y=a[i].y;
			if(!vis[y]) vis[y]=1,q.push(y);
		}
	}
	if(!vis[s]) return false;
	q.push(s);vis2[s]=1;
	while(!q.empty())
	{
		int x=q.front();q.pop();
		for(RE int i=link1[x];i;i=a[i].next)
		{
			int y=a[i].y;
			if(!vis[y]) return false;
			if(!vis2[y]) 
			{
				vis2[y]=1;
				if(y!=t) q.push(y);	
			}
		}
	}
	return true;
}

inline void tarjan(int x)
{
	dfn[x]=low[x]=++num;
	vis[q[++top]=x]=1;
	for(RE int i=link1[x];i;i=a[i].next)
	{
		int y=a[i].y;
		if(!dfn[y])
		{
			tarjan(y);
			low[x]=min(low[x],low[y]);
		}
		else if(vis[y]) low[x]=min(low[x],dfn[y]);
	}
	if(dfn[x]==low[x])
	{
		int k=0;++o;
		while(k!=x)
		{
			k=q[top--];
			belong[k]=o;
			vis[k]=0;
			v[o].pb(k);
		}
	}
}

inline void gauss()
{
	rep(i,1,num)
	{
		rep(j,i+1,num) if(fabs(c[j][i])>1e-8)
		{
			rep(k,1,num+1) swap(c[j][k],c[i][k]);
			break;
		}
		rep(j,1,num)
		{
			if(i==j) continue;
			db rate=c[j][i]/c[i][i];
			rep(k,1,num+1) c[j][k]-=rate*c[i][k];
		}
	}
}

int main()
{
	//freopen("1.in","r",stdin);
	get(n);get(m);get(s);get(t);
	rep(i,1,m)
	{
		int get(x),get(y);
		add(link1,x,y);add(link2,y,x);
		du[x]++;
	} 
	if(!bfs()) {puts("INF");return 0;}
	memset(vis,0,sizeof(vis));
	tarjan(s);
	rep(i,1,o)//tarjan的正序就是拓扑序. 
	{
		num=0;
		rep(j,0,v[i].size()-1) pos[v[i][j]]=++num;//对一个scc中的点编号. 
		rep(j,1,num+1) rep(k,1,num+1) c[j][k]=0;
		rep(j,0,v[i].size()-1)
		{
			int x=v[i][j],p=pos[x];
			c[p][p]=1;
			if(x==t) continue;//如果当前为t的话,期望直接是0. 
			c[p][num+1]=1;
			for(RE int k=link1[x];k;k=a[k].next)
			{
				int y=a[k].y;
				if(belong[y]^i) c[p][num+1]+=f[y]/du[x];
				else c[p][pos[y]]+=-1.0/du[x];
			}
		}
		gauss();
		rep(j,0,v[i].size()-1) 
		{
			int x=v[i][j];
			f[x]=c[pos[x]][num+1]/c[pos[x]][pos[x]];
		}	
	}
	printf("%.3lf",f[s]);
	return 0;
}


2020/6/2 22:00
加载中...