这模版敲了我俩个小时+写注释,参考自kuangbin!
两百行的大模拟,累死了QAQ
下面附上模版!
1 #include <bits/stdc++.h>
2 using namespace std;
3 const int maxn=50;
4 typedef long long ll;
5 int a[maxn][maxn];///增广矩阵
6 int x[maxn];///解集
7 bool free_x[maxn];///标记是否是不确定的变元
8 /*
9 void debug(void)
10 {
11 int i,j;
12 for(i=0;i<equ;i++)
13 {
14 for(j=0;j<var+1;j++)
15 {
16 cout<<a[i][j]<<" ";
17 }
18 cout<<endl;
19 }
20 cout<<endl;
21 }
22 */
23 inline int read()
24 {
25 int x=0,f=1;
26 char ch=getchar();
27 while(ch<'0'||ch>'9')
28 {
29 if(ch=='-')
30 f=-1;
31 ch=getchar();
32 }
33 while(ch>='0'&&ch<='9')
34 {
35 x=x*10+ch-'0';
36 ch=getchar();
37 }
38 return x*f;
39 }
40 inline void write(int x)
41 {
42 if(x<0)
43 {
44 putchar('-');
45 x=-x;
46 }
47 if(x>9)
48 write(x/10);
49 putchar(x%10+'0');
50 }
51 inline int gcd(int a,int b)///最大公约数
52 {
53 return b==0?a:gcd(b,a%b);
54 }
55 inline int lcm(int a,int b)///最小公倍数
56 {
57 return a/gcd(a,b)*b;///先除后乘防溢出
58 }
59 ///高斯消元法解方程组【-2表示有浮点型解,无整数解】
60 ///【-1表示无解,0表示唯一解,大于0表示无穷解,并返回自由元的个数】
61 ///【有equ方程,var个变元,增广矩阵行数为equ,分别为0->equ-1,列数为var+1,分别为0->var】
62 int Gauss(int equ,int var)
63 {
64 int i,j,k;
65 int max_r;///当前这列绝对值最大的行
66 int col;///当前处理的列
67 int ta,tb;
68 int LCM;
69 int temp;
70 int free_x_num;
71 int free_index;
72 for(i=0;i<=var;i++)
73 {
74 x[i]=0;
75 free_x[i]=true;
76 }
77 ///转化为阶梯型矩阵
78 col=0;///处理当前列
79 for(k=0;k<equ&&col<var;k++,col++)///枚举当前处理的行
80 {
81 ///找到该col列元素绝对值最大的那一行与第k行交换(为了在除法时减小误差)
82 max_r=k;
83 for(i=k+1;i<equ;i++)
84 {
85 if(abs(a[i][col])>abs(a[max_r][col]))
86 max_r=i;
87 }
88 if(max_r!=k)
89 {
90 ///与第k行交换
91 for(j=k;j<var+1;j++)
92 {
93 swap(a[k][j],a[max_r][j]);
94 }
95 }
96 if(a[k][col]==0)
97 {
98 ///说明该col列第k行以下全是0了,则处理当前行的下一列
99 k--;
100 continue;
101 }
102 for(i=k+1;i<equ;i++)
103 {
104 ///枚举要删除的行
105 if(a[i][col]!=0)
106 {
107 LCM=lcm(abs(a[i][col]),abs(a[k][col]));
108 ta=LCM/abs(a[i][col]);
109 tb=LCM/abs(a[k][col]);
110 if(a[i][col]*a[k][col]<0)
111 tb=-tb;///异号情况是相加
112 for(j=col;j<var+1;j++)
113 {
114 a[i][j]=a[i][j]*ta-a[k][j]*tb;
115 }
116 }
117 }
118 }
119 ///debug();
120 ///无解的情况:化简的增广矩阵中存在(0,0,......a)这样的行(a!=0)
121 for(i=k;i<equ;i++)
122 {
123 if(a[i][col]!=0)
124 return -1;
125 }
126 ///对于无穷解来说,如果要判断哪些是自由元,那么初等变换中的交换就会影响,则要记录交换
127 ///无穷解的情况:在var*(var+1)的增广矩阵中,出现(0,0,......0)这样的行,即说明没有形成严格的上三角阵
128 ///且目前出现的行数即为自由元的个数
129 if(k<var)
130 {
131 ///首先,自由元有var-k个,即不确定的变元至少有var-k个
132 for(i=k-1;i>=0;i--)
133 {
134 ///第i行一定不会是(0,0,......0)的情况,因为这样的行是在第k行到第equ行
135 ///同样,第i行一定不会是(0,0,......a),(a!=0)这样的情况无解
136 free_x_num=0;///用于判断该行中的不确定的变元的个数,如果超过1就无法求解它们仍为不确定的变元
137 for(j=0;j<var;j++)
138 {
139 if(a[i][j]!=0&&free_x[j]!=0)
140 {
141 free_x_num++;
142 free_index=j;
143 }
144 }
145 if(free_x_num>1)
146 continue;///无法求出确定的变元
147 ///说明只有一个不确定的变元free_index,那么可以求解出该变元,且该变元是确定的,
148 temp=a[i][var];
149 for(j=0;j<var;j++)
150 {
151 if(a[i][j]!=0&&j!=free_index)
152 temp-=a[i][j]*x[j];
153 }
154 x[free_index]=temp/a[i][free_index];///求出该变元
155 free_x[free_index]=0;///该变元是确定的
156 }
157 return var-k;
158 }
159 ///唯一解的情况:在var*(var+1)的增广矩阵中形成严格的上三角形
160 ///求出Xn-1,Xn-2,......X0
161 for(i=var-1;i>=0;i--)
162 {
163 temp=a[i][var];
164 for(j=i+1;j<var;j++)
165 {
166 if(a[i][j]!=0)
167 temp-=a[i][j]*x[j];
168 }
169 if(temp%a[i][i]!=0)
170 return -2;///说明有浮点数解,但无整数解
171 x[i]=temp/a[i][i];
172 }
173 return 0;
174 }
175 int main(void)
176 {
177 ///freopen("in.txt","r",stdin);
178 ///freopen("out.txt","w",stdout);
179 int i,j;
180 int equ,var;
181 while(equ=read(),var=read())
182 {
183 memset(a,0,sizeof(a));
184 for(i=0;i<equ;i++)
185 {
186 for(j=0;j<var+1;j++)
187 {
188 a[i][j]=read();
189 }
190 }
191 ///debug();
192 int free_num=Gauss(equ,var);
193 if(free_num==-1)
194 printf("No solution\n");///无解
195 else if(free_num==-2)
196 printf("There are floating point numbers, no integer solutions\n");///有浮点数解,无整数解
197 else if(free_num>0)
198 {
199 printf("The number of variables of infinite solution is:%d\n",free_num);///无穷多解,自由变元个数为
200 for(i=0;i<var;i++)
201 {
202 if(free_x[i]!=0)
203 printf("x%d is not sure\n",i+1);
204 else
205 printf("x%d:%d\n",i+1,x[i]);
206 }
207 }
208 else
209 {
210 for(i=0;i<var;i++)
211 printf("x%d:%d\n",i+1,x[i]);
212 }
213 printf("\n");
214 }
215 return 0;
216 }