#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #include<vector> const int N=3005; using namespace std; int first[N],nex[N],to[N],tot,vis[N],du[N];double sum[N],g[N],f[N]; void add(int a,int b){ to[++tot]=b;nex[tot]=first[a];first[a]=tot; } void dfs(int x){ g[x]=1.0;vis[x]=1; for(int i=first[x];i;i=nex[i]){ int y=to[i]; dfs(y); g[x]+=1.0/du[x]*g[y]; } } int main(){ int T; scanf("%d",&T); while(T--){ memset(du,0,sizeof(du)); //memset(sum,0,sizeof(sum)); memset(g,0,sizeof(g));tot=0; int n,m,p; scanf("%d%d%d",&n,&m,&p); for(int i=1;i<=m-n;i++){ int a,b; scanf("%d%d",&a,&b); add(a,b); du[a]++; } for(int i=1;i<=n;i++) du[i]++; for(int i=n+1;i<=m;i++){ if(vis[i]) continue; dfs(i); } for(int i=1;i<=n;i++){ sum[i]=0.0; for(int j=first[i];j;j=nex[j]){ //if(j>n&&j<=m) if(to[j]>n&&to[j]<=m) sum[i]+=g[to[j]]; } } f[n]=0.0; for(int i=n-1;i>=1;i--){ f[i]=f[i+1]+sum[i]+du[i]; //cout<<g[i]<<" "; } //for(int i=n+1;i<=m;i++) /*cout<<i<<" ",*/printf("%.4lf ",g[i]); printf("%.4lf\n",f[1]); } }
bzoj 4899 记忆的轮廓 题解(概率dp+决策单调性优化) (2)
内容版权声明:除非注明,否则皆为本站原创文章。