P3232 [HNOI2013]游走

给出无向图包括( 500 500 500)点，( 1.25 e 5 1.25e5 1.25e5)边，从 1 1 1点出发，到 n n n点结束，对于每条边进行任意编号，求出它所有边的期望和 ∑ i = 1 m p i × n u m i sum_{i=1}^{m}p_i times num_i ∑i=1m​pi​×numi​。

边概率–>点概率
可以想到期望和概率，我们可以发现除了 1 1 1点比较特殊, n n n点非常特殊，其他的点性质就相同了,我们先尝试把所有点同时考虑，发现对于 n n n点根本无法考虑，因为到 n n n点就停了，概率没法传给任何点。

我们尝试把 1 ∼ n − 1 1 thicksim n-1 1∼n−1的点整体考虑，发现每个点的概率见都存在依赖关系。
我们可以想到高斯消元:P3389 【模板】高斯消元法。

然后就可以比较方便的对于每一个点的期望访问次数列出方程:

对于点 i i i： a i 1 × p 1 + a i 2 × p 2 + . . . + − p i + . . . + a i n − 1 × p n − 1 + a i n × p n = 0 a_{i_1} times p_1+a_{i_2} times p_2+...+-p_i+...+a_{i_{n-1}} times p_{n-1}+a_{i_n} times p_n=0 ai1​​×p1​+ai2​​×p2​+...+−pi​+...+ain−1​​×pn−1​+ain​​×pn​=0

对于点 1 1 1： − p 1 + a 2 × p 2 + . . . + a n − 1 × p n − 1 + a n × p n = − 1 -p_1+a_2 times p_2+...+a_{n-1} times p_{n-1}+a_n times p_n=-1 −p1​+a2​×p2​+...+an−1​×pn−1​+an​×pn​=−1

为什么对于点 1 1 1，为什么是 − 1 -1 −1，因为 p 1 p_1 p1​表示的是点 1 1 1的总期望，出去返回的情况就是点 1 1 1的初始期望为 1.0000000000 1.0000000000 1.0000000000

所以这个方程便可以顺利的解了。

code:

#include
#define ll long long
#define fd(i, a, b) for (ll i = a; i >= b; i--)
#define r(i, a) for (ll i = fir[a]; i; i = e[i].nex)
#define file(a) freopen(#a ".in", "r", stdin);
#define il inline
#define db double
#define gc getchar()
#define f(i,a,b) for(ll i=a;i<=b;i++)
using namespace std;
const ll maxn=5e2+10,INF=1e16,maxm=2e5;
il ll read(){
    ll x=0,f=1;char ch=gc;
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=gc;}
    while(ch>='0'&&ch<='9') x=(x*10)+(ch^48),ch=gc;
    return x*f;
}
ll cnt;
struct edge{ll to,from;}e[maxm<<1];
il void add(ll a,ll b){e[++cnt].to=b,e[cnt].from=a;}
ll n,m;
db g[maxn][maxn],out[maxn],one=1.0000000000;
il void guess(){
    n--;
    f(i,1,n){
        ll M=i;
        f(j,i+1,n) if(fabs(g[j][i])>fabs(g[M][i])) M=j;
        swap(g[M],g[i]);
        f(j,1,n){
            if(j==i) continue;
            db tmp=g[j][i]/g[i][i];
            f(k,i+1,n+1) g[j][k]-=tmp*g[i][k];
        }
    }
    n++;
}
db p[maxm];
int main()
{
    n=read()
    ;m=read();
    f(i,1,m){
        ll a=read(),b=read();
        add(a,b);
        out[a]++,out[b]++;
    }
    g[1][n]=-1;
    f(i,1,n-1) g[i][i]=-1;
    f(i,1,m){
        ll a=e[i].to,b=e[i].from;
        if(a==n||b==n) continue;
        g[a][b]=(one/out[b]);
        g[b][a]=(one/out[a]);
    }
    guess();
    f(i,1,n-1) g[i][n]/=g[i][i];
    f(i,1,m){
        ll a=e[i].to,b=e[i].from;
        p[i]=g[a][n]/out[a]+g[b][n]/out[b];
    }
    // f(i,1,m) cout<