【BZOJ 3470】3470: Freda’s Walk 期望

【分析】

　　测试考这题。。错误打法 考场上竟然AC了【黑人问号脸？？

　　也算给自己提个醒吧，DAG和树终究是不一样的。不能f[i][0]和f[i][1]表示后面割还是没割，比如：

　　

　　割3后面那条边是f[2][1]和f[3][1]，但是不会让他们转移到f[1][1]，因为你规定只有一个儿子可以选割，但是是可以的，因为只是个割了3下面那条边。。

　　所以这个方法不行。

　　考虑割一条边对答案的影响。

　　假设割x->y,只会影响f[x]以及1到x路径上的点。

　　但是我们只需要知道x的f值的改变对1这个点的f值的影响。

　　假设从1走到x的概率是p，假设那么f[1]会增加(f[x]'-f[x])*p,直接枚举割哪条边然后计算出这个求max就好了。

　　【ORZORZORZ...

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 #include<cmath>

 using namespace std;

 #define Maxn 100010

 #define Maxm 1000010

 struct node

 {

     int x,y,c,next,p;

 }t[Maxm],tt[Maxm];

 int first[Maxn],len;

 int d[Maxn];

 int ft[Maxn];

 void ins(int x,int y,int c)

 {

     t[++len].x=x;t[len].y=y;t[len].c=c;

     t[len].next=first[x];first[x]=len;t[len].p=;

     tt[len].x=y;tt[len].y=x;tt[len].c=c;tt[len].next=ft[y];ft[y]=len;

 }

 bool vis[Maxn];

 double g[Maxn];

 void dfs2(int x)

 {

     if(vis[x]) return;vis[x]=;

     if(x==) {g[x]=;return;}

     for(int i=ft[x];i;i=tt[i].next)

     {

         int y=tt[i].y;

         dfs2(y);

         g[x]+=g[y]*tt[i].c*1.0/d[y];

     }

 }

 double f[Maxn];

 void dfs(int x)

 {

     if(vis[x]) return;vis[x]=;

     f[x]=;

     for(int i=first[x];i;i=t[i].next) if(t[i].p)

     {

         int y=t[i].y;

         dfs(y);

         f[x]+=(f[y]+)*t[i].c*1.0/d[x];

     }

     return;

 }

 int main()

 {

     int n,m;

     scanf("%d%d",&n,&m);

     len=;

     memset(first,,sizeof(first));

     memset(ft,,sizeof(ft));

     for(int i=;i<=m;i++)

     {

         int x,y,c;

         scanf("%d%d%d",&x,&y,&c);

         x++;y++;

         d[x]+=c;

         ins(x,y,c);

     }

     memset(vis,,sizeof(vis));

     for(int i=;i<=n;i++) g[i]=;

     for(int i=;i<=n;i++) dfs2(i);

     memset(vis,,sizeof(vis));

     dfs();

     double mx=f[];

     for(int i=;i<=len;i++)

     {

         int x=t[i].x,y=t[i].y;

         double ad;

         if(d[x]!=t[i].c) ad=(f[x]*d[x]*1.0/(d[x]-t[i].c)-(f[y]+)*t[i].c*1.0/(d[x]-t[i].c))-f[x];

         else ad=-f[x];

         mx=max(mx,f[]+g[x]*ad);

     }

     printf("%.6lf\n",mx);

     return ;

 }

2017-04-24 18:51:22