传递闭包+求概率——列项相消法lightoj1321好题

主要是要想到边与边的通过概率是独立的，所以先求出最终的概率，然后用推出的公式求总期望即可

最终概率E[0][n-1]，可以用传递闭包来做

裂项相消法都不会了。。

/*
闭包上推期望
每条边都具有独立性，算出每条边上成功通过的期望 Ei=2K/pi(裂项相消法)
然后再通过佛洛依德进行传递边之间的关系即可
直接求期望比较麻烦，先求最大的概率 
*/
#include<bits/stdc++.h>
using namespace std;
int n,m,S,K,t;
double mp[120][120];//概率矩阵 

void floyed(){
    for(int i=0;i<n;i++)mp[i][i]=1;
    for(int k=0;k<n;k++)
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)
                mp[i][j]=max(mp[i][j],mp[i][k]*mp[k][j]); 
}

int main(){
    cin>>t;
    for(int tt=1;tt<=t;tt++){
        memset(mp,0,sizeof mp);
        cin>>n>>m>>S>>K;
        for(int i=1;i<=m;i++){
            int u,v;double w;
            cin>>u>>v>>w;
            mp[u][v]=mp[v][u]=w/100;//通过一条边的概率 
        }
        floyed();
        printf("Case %d: %.10lf
",tt,2.0*S*K/mp[0][n-1]);
    }
}