高斯消元(模板)

发表于 | 分类于 |

没啥讲的，纯模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
void gauss()
{
    int n;
    cin>>n;
    vector<vector<double>> a(n,vector<double>(n+1));
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<=n;j++)//多出一维增广矩阵
        {
            cin>>a[i][j];
        }
	}
    for(int i=0;i<n;i++)
    {
        int mx=i;
        for(int j=i+1;j<n;j++)//找出第i列中最大元素
        {
            if(fabs(a[j][i])>fabs(a[mx][i]))
            {
                mx=j;
            }
		}
        swap(a[mx],a[j]);//将最大元素所在行换到第i行
        if(fabs(a[i][i])<1e-9)//该列元素都为0的情况
        {
            cout<<"No ans!"
        }
        for(int j=0;j<n;j++)
        {
            if(j!=i)
            {
                double tmp=a[j][i]/a[i][i];
                for(int k=i;k<=n;k++)
                {
                    a[j][k]-=a[i][k]*tmp;
                }
            }
        }
    }
}

莫名奇妙上面一个写挂了。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
void gauss()
{
    ll n;
    cin >> n;
    vector<vector<double>> a(n + 1, vector<double>(n + 1));
    vector<vector<double>> b(n + 1, vector<double>(n + 1));
    for (ll i = 0; i <= n; i++)
    {
        for (ll j = 0; j < n; j++)
        {
            cin >> b[i][j]; //第i个点的第j维
        }
    }
    for (ll i = 0; i <n; i++)
    {
        a[i][n] = 0;
        for (ll j = 0; j < n; j++)
        {
            a[i][j] = -2 * (b[i][j] - b[(i + 1) % (n + 1)][j]);
            a[i][n] += b[(i + 1) % (n + 1)][j] * b[(i + 1) % (n + 1)][j];
            a[i][n] -= b[i][j] * b[i][j];
        }
    }
    for (ll i = 0; i < n;i++)
    {
        for (ll j = i; j < n;j++)
        {
            if(fabs(a[j][i])>1e-8)
            {
                swap(a[i], a[j]);//使a[i][i]>1e-8
            }
        }
        for (ll j = 0; j < n;j++)
        {
            if(i==j)
            {
                continue;
            }
            double rate = a[j][i] / a[i][i];
            for (ll k = i; k <= n;k++)
            {
                a[j][k] -= a[i][k] * rate;
            }
        }
    }
    for (ll i = 0; i < n;i++)
    {
        cout<<a[i][n]/a[i][i]<<" ";
    }
    cout << "\n";
}

题面:https://www.acwing.com/problem/content/209/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
void gauss()
{
    vector<vector<ll>> a(m + 1, vector<ll>(n + 2, 0));
    // vector<ll> c(n + 1);
    ll ans = 0;
    ll num = 0;
    string str1, str2;
    for (ll i = 1; i <= m; i++)
    {
        cin >> k;
        cin >> str1 >> str2;
        a[i][n + 1] = (mp[str2] - mp[str1] + 8) % 7;
        for (ll j = 1; j <= k; j++)
        {
            cin >> num;
            a[i][num] = (a[i][num] + 1) % 7;
        }
    }
    /*for (ll i = 1; i <= m; i++)
    {
        for (ll j = 1; j <= n + 1; j++)
        {
            cout << a[i][j] << " ";
        }
        cout << "\n";
    }*/
    // sort(a.begin() + 1, a.begin() + n + 1,cmp);
    ll row = 1, col = 1;
    //vector<ll> pos;
    for (row = 1, col = 1;row<=m&&col<=n; row++,col++)
    {
        for (ll j = row; j <= m; j++)
        {
            if (a[row][col] == 0 && a[j][col] != 0)
            {
                swap(a[row], a[j]);
                break;
            }
        }
        if (a[row][col] == 0)
        {
            row--;
            ans = 1;//出现自由元
            continue;
        }
        //pos.push_back(col);
        for (ll j = 1; j <= m; j++)
        {
            if (row == j || a[j][col] == 0)
            {
                continue;
            }
            // double rate = a[j][i] / a[i][i];
            ll rate1 = a[j][col] / gcd(a[j][col], a[row][col]);
            ll rate2 = a[row][col] / gcd(a[j][col], a[row][col]);
            for (ll k = 1; k <= n + 1; k++)
            {
                a[j][k] = (a[j][k] * rate2 - a[row][k] * rate1)%7;
            }
            
        }
    }
    for (ll i = 1; i <= m; i++)
    {
        ll flag = 0;
        for (ll j = 1; j <= n; j++)
        {
            if(a[i][j]!=0)
            {
                flag = 1;
                break;
            }
        }
        if (flag == 0 && a[i][n + 1]%7!= 0)
        {
            ans = 2;
        }
    }
    if(ans==0&&n>m)
    {
        ans = 1;
    }
    /*for (ll i = 1; i <= m; i++)
    {
        for (ll j = 1; j <= n + 1; j++)
        {
            cout << a[i][j] << " ";
        }
        cout << "\n";
    }*/
    if (ans == 2)
    {
        cout << "Inconsistent data.\n";
    }
    else if (ans == 1)
    {
        cout << "Multiple solutions.\n";
    }
    else
    {
        for (ll i = 1; i <= n; i++)
        {
            ll ret = (quick(a[i][i]%7, 5) * a[i][n + 1] % 7 + 7) % 7;
            //ret = (ret + 7) % 7 + 3;
            if(ret<3)
            {
                ret = ret + 7;
            }
            cout << ret << " ";
        }
        cout << "\n";
    }
    // cout << num << " " << ans << "\n";
}

该模板适用于整数mod7方程组，且使用了row、col两个变量来分辨无解、多解的情况

题面:https://www.acwing.com/problem/content/description/229/