3 条题解

  • 0
    @ 2016-05-06 20:42:33

    用了long double死活过不了..
    用了double就直接过了..

    不知所措..

  • 0
    @ 2015-10-05 23:23:27

    提示很多因为精度问题错误的用户。

    既然每一行中每一项都要除以deg(x),为何你不每一项都乘上deg(x)?
    之后 所有系数都是整数 了,这样精度就足够了。
    对于整系数的方程组,甚至可以用 辗转相减 去消元。

    • @ 2016-03-24 20:24:25

      好有道理!!!
      学习啦~~~

  • 0
    @ 2015-10-04 00:06:38

    我竟然是第一个发题解的。。。用的是高斯消元,没啥优化
    PS:注意精度
    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<cmath>
    #include<algorithm>
    #include<vector>
    using namespace std;
    const int MAXN = 2000 + 10;

    double f[MAXN][MAXN], ans;
    int n, m;
    vector<pair<int, int> > map[MAXN];

    void Gauss(){
    int bri = 1;
    for(int i=1; i<n-1; i++){
    for(int k=i+1; k<n; k++){
    double x = f[k][bri]/f[i][bri];
    for(int j=0; j<n; j++)
    f[k][j] -= f[i][j] * x;
    }
    bri++;
    }
    ans = f[n-1][0]/f[n-1][n-1], bri = n-1;
    for(int i=n-2; i>=1; i--){
    for(int j=i-1; j>=1; j--)
    f[j][0] -= f[j][bri]*ans;

    ans = (f[i][0] - f[i][bri]*ans) / f[i][bri-1];
    bri--;
    }
    }

    int main()
    {
    scanf("%d%d", &n, &m);
    for(int i=1; i<=m; i++){
    int x, y, w;
    scanf("%d%d%d", &x, &y, &w);
    if(x != y){

    map[x].push_back(make_pair(y, w));
    map[y].push_back(make_pair(x, w));
    }
    else
    map[x].push_back(make_pair(x, w));
    }
    for(int i=1; i<n; i++){
    int len = map[i].size();
    f[i][0] = 0;
    for(int j=0; j<map[i].size(); j++){
    f[i][map[i][j].first] = -1;
    f[i][0] += map[i][j].second;
    }
    f[i][i] += len;
    }
    Gauss();
    printf("%.1f", ans+1e-5);
    return 0;
    }

  • 1

信息

ID
1966
难度
8
分类
d 点击显示
标签
(无)
递交数
500
已通过
42
通过率
8%
上传者