牛客练习赛12 D 图图（高斯消元）

69 阅读 0 评论 46 点赞

我是靠谱客的博主粗犷冰棍，最近开发中收集的这篇文章主要介绍牛客练习赛12 D 图图（高斯消元），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

点击打开链接

解析：nge

这道题其实是一道高斯消元的数学题，用里面的边的信息来构建n个未知数的方程组，具体的细节我注释在代码里了。看了大神的代码，里面有一个关键的细节，就是对出度为0的点(下面称为终点)的处理——加一条自环边。我感觉是因为防止无解或错解情况的发生。因为当有出度为0的点出现时，一定是有答案的（终点概率为1，其他点概率为0）。但如果不处理的话，终点的概率就完全取决于其他点的概率了。因为方程就变为z=a1x1+a2x2+...（x1,x2..为未知量，且方程里面没有常数项，且z只在这个方程出现，系数为1），当其他所有的点概率为0时，那么解出来终点的概率一定为0，但总的概率和要为1，所以答案是不符合的。因此，当终点出现时，将自环边加进去，那么方程就变为0=a1x1+a2x1+...，这样，终点的概率设成1，就是答案了。

下面有两组数据，来理解这个自环边

4 3
0 1 2
0 2 3
0 3 4
3 3
0 0 1
0 1 2
1 2 3

#include <bits/stdc++.h>
using namespace std;
#define eps 1e-12
const int MAXN = 1e4+10;

typedef long long int lli;

int edge[MAXN][3];

lli outw[MAXN];
int flag;
int n;

double equ[MAXN][MAXN];

//高斯－若尔当消元法
//当出现有无穷多解时，自动处理，取一个自由未知量的值为1，其余为0

void Gauss() {  //高斯－若尔当消元法
    for(int i=0;i<=n;i++) {  //消到第i行第i列，就是要把在第i行一下的所有行的第i列变成0，这样才能变成阶梯型
        int r=i;
        for(int j=i+1;j<=n;j++) if(fabs(equ[j][i])>fabs(equ[r][i])) r=j;
        if(fabs(equ[r][i])<eps) continue;
        if(r!=i) for(int j=0;j<=n;j++) swap(equ[r][j],equ[i][j]);  //找到第i列中的最大的元素，并将它与第i行交换
        for(int k=0;k<=n;k++) {  //高斯－若尔当消元法精华部分，除了i行,所有行都变换一遍
            if(k!=i) for(int j=n;j>=i;j--) equ[k][j]-=equ[k][i]/equ[i][i]*equ[i][j];
        //将第k行的各元素根据第i列元素与第I行第i列元素的比值进行变换
        }
    }
}


int main()
{
    int m;
    scanf("%d%d",&n,&m);
    int p,q,r;
    for(int i=0;i<m;i++)
    {
        scanf("%d%d%d",&p,&q,&r);
        edge[i][0]=p;
        edge[i][1]=q;
        edge[i][2]=r;
        outw[p]+=r;
    }
    //入度为0的点的概率一定是0，因为没有任何点可以到达这个点，所以答案在该点的概率永远为0
    //对于出度为0的点，其实我们只要任选其中的一个概率为1就是答案了，而如果不加自环这条边的话
    //很容易出现非法或错误的答案
    for(int i=0;i<n;i++)
    {
        if(!outw[i])
        {
            outw[i]=1;
            edge[m][0]=edge[m][1]=i;
            edge[m][2]=1;
            m++;
        }
    }
    for(int i=0;i<m;i++)
    {
        equ[edge[i][1]][edge[i][0]]+=edge[i][2]*1.0/outw[edge[i][0]];
    }
    for(int i=0;i<n;i++)
    {
        equ[i][i]-=1;
        equ[n][i]=1;
    }
    equ[n][n]=1;
    flag=0;
    Gauss ();
    for(int i=0;i<n;i++)
    {
        if(fabs(equ[i][i])<eps&&fabs(equ[i][n])>eps) flag=1;  //如果某行的方程式0=k（k>0），则无解
    }
    if(fabs(equ[n][n])>eps) flag=1;  //因为总共只有n个未知数,不过去掉也好像能过
    if(flag) printf("Impossiblen");
    else
    {
        for(int i=0;i<n;i++)
        {
            if(fabs(equ[i][n])<eps) printf("%.20lfn",0.0);
            else printf("%.20lfn",equ[i][n]/equ[i][i]);
        }
    }
    return 0;
}