bzoj2419

http://www.lydsy.com/JudgeOnline/problem.php?id=2419

∑Ui−UjRi,j=0∑Ui−UjRi,j=0

∑U1−UjR1,j=1∑U1−UjR1,j=1

∑Un−UjRi,n=−1∑Un−UjRi,n=−1

Un=0

这就是方程了。。。但是代码有点不理解

#include<bits/stdc++.h>

using namespace std;

const int N = ;

double a[N][N], g[N][N];

int n, m;

void build()

{

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

        for(int j = ; j <= n; ++j)

            a[i][i] += g[i][j], a[i][j] -= g[i][j];

    a[][n + ] = 1.0;

    a[n][n + ] = -1.0;

    a[n][n] += 1.0;

}

void gauss_jordan()

{

    for(int now = ; now <= n; ++now)

    {

        int x = now;

        for(int i = now + ; i <= n; ++i) if(fabs(a[i][now]) > fabs(a[x][now])) x = i;

        for(int i = ; i <= n + ; ++i) swap(a[now][i], a[x][i]);

        double t = a[now][now];

        for(int i = now; i <= n + ; ++i) a[now][i] /= t;

        for(int i = ; i <= n; ++i) if(i != now)

        {

            double t = a[i][now];

            for(int j = now; j <= n + ; ++j) a[i][j] -= t * a[now][j];

        }

    }

}

int main()

{

    while(scanf("%d%d", &n, &m) != EOF)

    {

        memset(a, , sizeof(a));

        memset(g, , sizeof(g));

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

        {

            int u, v; double r; scanf("%d%d%lf", &u, &v, &r);

            if(u == v) continue;

            g[u][v] += 1.0 / r; g[v][u] += 1.0 / r;

        }

        build();

        gauss_jordan();

        printf("%.2f\n", a[][n + ]);

    }

    return ;

}