绿豆蛙的归宿

  1 #include<cstdio>
  2 #include<iostream>
  3 #include<cstring>
  4 #include<queue>
  5 #define mem(a,b) memset(a,b,sizeof(a))
  6 #define dd double
  7 using namespace std;
  8 int read()
  9 {
 10     int ans=0;char q=getchar();
 11     while(q<'0'||q>'9')q=getchar();
 12     while(q>='0'&&q<='9'){ans=ans*10+q-'0';q=getchar();}
 13     return ans;
 14 }
 15 const int N=100010;
 16 struct son
 17 {
 18     int v,next,w;
 19 };
 20 son a1[N<<1];
 21 int first[N<<1],e;
 22 
 23 void addbian(int u,int v,int w)
 24 {
 25     a1[e].w=w;
 26     a1[e].v=v;
 27     a1[e].next=first[u];
 28     first[u]=e++;
 29 }
 30 
 31 int n,m;
 32 int u,o,p;
 33 double indegree[N],outdegree[N];
 34 int tuo[N],now;
 35 double f[N];
 36 double ans;
 37 double gai[N];
 38 queue<int> q;
 39 
 40 void qiutuo()
 41 {
 42     tuo[++now]=1;
 43     q.push(1);
 44     while(!q.empty())
 45     {
 46         int k=q.front();
 47         q.pop();
 48         for(int i=first[k];i!=-1;i=a1[i].next)
 49         {
 50             int temp=a1[i].v;
 51             --indegree[temp];
 52             if(!indegree[temp])
 53             {
 54                 tuo[++now]=temp;
 55                 q.push(temp);
 56             }
 57         }
 58     }
 59 }
 60 
 61 void out11()
 62 {
 63     printf("
");
 64     for(int i=1;i<=n;++i)
 65       printf("%d ",tuo[i]);
 66     printf("
");
 67     for(int i=1;i<=n;++i)
 68       printf("%.0lf ",indegree[i]);
 69     printf("
");
 70     for(int i=1;i<=n;++i)
 71       printf("%.0lf ",outdegree[i]);
 72     printf("
");
 73     for(int i=1;i<=n;++i)
 74       printf("%.2lf ",f[i]);
 75     printf("
");
 76 }
 77 
 78 int main(){
 79     //freopen("1.txt","r",stdin);
 80     freopen("ldfrog.in","r",stdin);
 81     freopen("ldfrog.out","w",stdout);
 82     mem(first,-1);
 83     n=read();m=read();
 84     for(int i=1;i<=m;++i)
 85     {
 86         u=read();o=read();p=read();
 87         ++indegree[o];
 88         ++outdegree[u];
 89         addbian(u,o,p);
 90     }
 91     
 92     for(int i=1;i<n;++i)
 93         gai[i]=(dd)1/outdegree[i];
 94     
 95     qiutuo();
 96     f[1]=1;
 97     for(int i=1;i<=n;++i)
 98         for(int j=first[tuo[i]];j!=-1;j=a1[j].next)
 99         {
100             int temp=a1[j].v;
101             f[temp]+=f[tuo[i]]*gai[tuo[i]];
102         }
103     
104     for(int i=1;i<=n;++i)
105         for(int j=first[i];j!=-1;j=a1[j].next)
106             ans+=(f[i]*gai[i]*(dd)a1[j].w);
107             
108     printf("%.2lf",ans);
109     
110     //out11();
111     
112 //    while(1);
113     return 0;
114 }
115     
116     
117     
118     
119     
120     
121     
122     
123     
124     
125     
126     
127     
128     
129     
130     
131     
132     
133     
134     
135     
136     
137
View Code