首页 > 代码库 > 高斯消元学习
高斯消元学习
POJ1222
id=1222" style="color:rgb(106,57,6); text-decoration:none">http://poj.org/problem?id=1222
一定有解,直接高斯消元搞定
[cpp] view plaincopy
- #include <iostream>
- #include <cmath>
- #include <cstdio>
- #include <cstring>
- using namespace std;
- const int maxn =30;
- int equ,var;
- int a[maxn+1][maxn+1],x[maxn];
- void Gauss(){
- int k,col;
- for(k=0,col=0;k<equ&&col<var;k++,col++){
- int mx=k;
- for(int i=k+1;i<equ;i++)
- if(a[i][col]>a[mx][col]) mx=i;
- if(mx!=k)
- for(int i=col;i<var+1;i++)
- swap(a[k][i],a[mx][i]);
- if(!a[k][col]){k--;continue;}
- for(int i=k+1;i<equ;i++){
- if(a[i][col]!=0){
- for(int j=col;j<var+1;j++)
- a[i][j]^=a[k][j];
- }
- }
- }
- for(int i=var-1;i>=0;i--){
- int tmp=a[i][var];
- for(int j=i+1;j<var;j++) tmp^=(a[i][j]&&x[j]);
- x[i]=tmp;
- }
- }
- void init(){
- memset(a,0,sizeof(a));
- memset(x,0,sizeof(x));
- for(int i=0;i<5;i++){
- for(int j=0;j<6;j++){
- if(i!=0) a[i*6+j][(i-1)*6+j]=1;
- if(i!=4) a[i*6+j][(i+1)*6+j]=1;
- if(j!=0) a[i*6+j][i*6+j-1]=1;
- if(j!=5) a[i*6+j][i*6+j+1]=1;
- a[i*6+j][i*6+j]=1;
- }
- }
- }
- int main()
- {
- int t,ca=1;
- cin>>t;
- while(t--){
- init();
- equ=var=30;
- for(int i=0;i<30;i++)
- cin>>a[i][30];
- Gauss();
- printf("PUZZLE #%d\n",ca++);
- for(int i=0;i<30;i++)
- {
- if(i%6!=0) putchar(‘ ‘);
- printf("%d",x[i]);
- if(i%6==5) puts("");
- }
- }
- return 0;
- }
POJ1681
id=1681" style="color:rgb(106,57,6); text-decoration:none; font-family:Arial; font-size:14px; line-height:26px">http://poj.org/problem?id=1681
高斯消元推断有没有解,然后二进制枚举自由变元 求最小值
[cpp] view plaincopy
- #include <iostream>
- #include <cstring>
- #include <cstdio>
- #include <cmath>
- using namespace std;
- const int maxn = 16*16;
- int a[maxn][maxn],x[maxn],n;
- int free_num,free_x[maxn],equ,var;
- char mp[20][20];
- void init()
- {
- memset(a,0,sizeof(a));
- memset(free_x,0,sizeof(free_x));
- memset(x,0,sizeof(x));
- free_num=0;
- for(int i=0;i<n;i++){
- for(int j=0;j<n;j++){
- if(i!=0) a[i*n+j][(i-1)*n+j]=1;
- if(i!=n-1) a[i*n+j][(i+1)*n+j]=1;
- if(j!=0) a[i*n+j][i*n+j-1]=1;
- if(j!=n-1) a[i*n+j][i*n+j+1]=1;
- a[i*n+j][i*n+j]=1;
- }
- }
- equ=var=n*n;
- }
- int Gauss()
- {
- int k,col;
- for(k=0,col=0;k<equ&&col<var;k++,col++){
- int mx=k;
- for(int i=k+1;i<equ;i++)
- if(a[i][col]>a[mx][col]) mx=i;
- if(k!=mx){
- for(int i=col;i<var+1;i++)
- swap(a[k][i],a[mx][i]);
- }
- if(!a[k][col]){
- k--;
- free_x[free_num++]=col;
- continue;
- }
- for(int i=k+1;i<equ;i++){
- if(a[i][col]!=0){
- for(int j=col;j<var+1;j++)
- a[i][j]^=a[k][j];
- }
- }
- }
- for(int i=k;i<equ;i++)
- if(a[i][col]) return -1;
- return var-k;
- }
- void solve()
- {
- int t=Gauss();
- //cout<<"t "<<t<<endl;
- if(t==-1){
- printf("inf\n");
- return ;
- }
- int ans;
- if(t==0){
- ans=0;
- for(int i=var-1;i>=0;i--){
- x[i]=a[i][var];
- for(int j=i+1;j<var;j++)
- x[i]^=(a[i][j]&&x[j]);
- ans+=x[i];
- }
- }
- else{
- ans=1000000000;
- /*cout<<"******"<<endl;
- for(int i=0;i<t;i++)
- cout<<free_x[i]<<" ";
- cout<<endl<<"*******"<<endl;*/
- for(int i=0;i<(1<<t);i++){
- int tmp=0;
- for(int j=0;j<t;j++){
- if(i&(1<<j)){
- x[free_x[j]]=1;
- tmp++;
- }
- else
- x[free_x[j]]=0;
- }
- for(int j=var-t-1,k;j>=0;j--){
- for(k=j;k<var;k++)
- if(a[j][k]) break;
- x[k]=a[j][var];
- for(int l=k+1;l<var;l++)
- x[k]^=(a[j][l]&&x[l]);
- tmp+=x[k];
- }
- ans=min(tmp,ans);
- }
- }
- printf("%d\n",ans);
- }
- int main()
- {
- int t;
- scanf("%d",&t);
- while(t--){
- scanf("%d",&n);
- init();
- for(int i=0;i<n;i++)
- scanf("%s",mp[i]);
- for(int i=0;i<n;i++){
- for(int j=0;j<n;j++){
- if(mp[i][j]==‘w‘)
- a[i*n+j][n*n]=1;
- }
- }
- solve();
- }
- return 0;
- }
POJ 1753 http://poj.org/problem?id=1753
同上
[cpp] view plaincopy
- #include <iostream>
- #include <cstring>
- #include <cstdio>
- using namespace std;
- const int maxn = 17;
- int equ,var,free_num,free_x[maxn];
- int a[maxn][maxn],x[maxn];
- char mp[4][4];
- void init()
- {
- memset(a,0,sizeof(a));
- memset(x,0,sizeof(x));
- var=equ=16;
- free_num=0;
- for(int i=0;i<4;i++){
- for(int j=0;j<4;j++){
- if(i!=0) a[i*4+j][(i-1)*4+j]=1;
- if(i!=3) a[i*4+j][(i+1)*4+j]=1;
- if(j!=0) a[i*4+j][i*4+j-1]=1;
- if(j!=3) a[i*4+j][i*4+j+1]=1;
- a[i*4+j][i*4+j]=1;
- }
- }
- }
- int Gauss()
- {
- int k,col;
- for(k=0,col=0;k<equ&&col<var;k++,col++){
- int mx=k;
- for(int i=k+1;i<equ;i++)
- if(a[i][col]>a[mx][col]) mx=i;
- for(int i=col;i<var+1;i++)
- swap(a[k][i],a[mx][i]);
- if(!a[k][col]){
- k--;
- free_x[free_num++]=col;
- continue;
- }
- for(int i=k+1;i<equ;i++){
- if(a[i][col]){
- for(int j=col;j<var+1;j++)
- a[i][j]^=a[k][j];
- }
- }
- }
- for(int i=k;i<equ;i++)
- if(a[i][col]) return -1;
- return var-k;
- }
- int calu()
- {
- int t=Gauss();
- //cout<<"t "<<t<<endl;
- if(t==-1) return -1;
- int ans;
- if(t==0){
- ans=0;
- for(int i=var-1;i>=0;i--){
- x[i]=a[i][var];
- for(int j=i+1;j<var;j++)
- x[i]^=(x[j]&&a[i][j]);
- ans+=x[i];
- }
- }
- else{
- ans=10000000;
- for(int i=0;i<(1<<t);i++){
- int tmp=0;
- for(int j=0;j<t;j++){
- if(i&(1<<j)){
- x[free_x[j]]=1;
- tmp++;
- }
- else
- x[free_x[j]]=0;
- }
- for(int j=var-t-1,k;j>=0;j--){
- for(k=j;k<var;k++)
- if(a[j][k]) break;
- x[k]=a[j][var];
- for(int l=k+1;l<var;l++)
- x[k]^=(a[j][l]&&x[l]);
- tmp+=x[k];
- }
- ans=min(ans,tmp);
- }
- }
- return ans;
- }
- int main()
- {
- while(~scanf("%s",mp[0])){
- scanf("%s%s%s",mp[1],mp[2],mp[3]);
- init();
- for(int i=0;i<4;i++){
- for(int j=0;j<4;j++){
- if(mp[i][j]==‘w‘)
- a[i*4+j][16]=0;
- else
- a[i*4+j][16]=1;
- }
- }
- int ans1=calu();
- init();
- for(int i=0;i<4;i++){
- for(int j=0;j<4;j++){
- if(mp[i][j]==‘b‘)
- a[i*4+j][16]=0;
- else
- a[i*4+j][16]=1;
- }
- }
- int ans2=calu();
- //cout<<"ans1 ans2 "<<ans1<<" "<<ans2<<endl;
- if(ans1>=0&&ans2>=0){
- cout<<min(ans1,ans2)<<endl;
- }
- else{
- if(ans1<0&&ans2<0)
- cout<<"Impossible"<<endl;
- else
- cout<<max(ans1,ans2)<<endl;
- }
- }
- return 0;
- }
id=1830" style="color:rgb(106,57,6); text-decoration:none; font-family:Arial; font-size:14px; line-height:26px">http://poj.org/problem?id=1830
求解的方案数 每一个变量有两种取值 则总数为2^x 个 x为自由变量的个数
[cpp] view plaincopy
- #include <iostream>
- #include <cstring>
- #include <cstdio>
- #include <cmath>
- using namespace std;
- int free_num,n;
- int a[30][30],s[30],e[30],x[30];
- int Gauss()
- {
- int k,col;
- for(k=0,col=0;k<n&&col<n;k++,col++){
- int mx=k;
- for(int i=k+1;i<n;i++)
- if(a[mx][col]<a[i][col]) mx=i;
- if(mx!=k){
- for(int i=col;i<n+1;i++)
- swap(a[k][i],a[mx][i]);
- }
- if(!a[k][col]){
- k--;
- continue;
- }
- for(int i=k+1;i<n;i++){
- if(a[i][col]!=0){
- for(int j=col;j<n+1;j++)
- a[i][j]^=a[k][j];
- }
- }
- }
- for(int i=k;i<n;i++){
- if(a[i][col]!=0)
- return -1;
- }
- return n-k;
- }
- int main()
- {
- int t;
- cin>>t;
- while(t--){
- cin>>n;
- for(int i=0;i<n;i++)
- cin>>s[i];
- for(int j=0;j<n;j++)
- cin>>e[j];
- int x,y;
- memset(a,0,sizeof(a));
- for(int i=0;i<n;i++)
- a[i][i]=1;
- while(1){
- cin>>x>>y;
- if(x==0&&y==0)
- break;
- a[y-1][x-1]=1;
- }
- for(int i=0;i<n;i++)
- a[i][n]=s[i]^e[i];
- int free_num=Gauss();
- if(free_num==-1)
- cout<<"Oh,it‘s impossible~!!"<<endl;
- else
- cout<<(1<<free_num)<<endl;
- Gauss();
- }
- return 0;
- }
POJ3185
id=3185" style="color:rgb(106,57,6); text-decoration:none; font-family:Arial; font-size:14px; line-height:26px">http://poj.org/problem?id=3185
一维的更简单 随便搞
[cpp] view plaincopy
- #include <iostream>
- #include <cstring>
- #include <cstdio>
- using namespace std;
- const int maxn = 21;
- int equ,var,free_num,free_x[maxn];
- int a[maxn][maxn],x[maxn],s[maxn];
- void init()
- {
- memset(a,0,sizeof(a));
- memset(x,0,sizeof(x));
- var=equ=20;
- free_num=0;
- for(int i=0;i<20;i++){
- a[i][i]=1;
- if(i!=0) a[i][i-1]=1;
- if(i!=19) a[i][i+1]=1;
- if(s[i]) a[i][20]=1;
- }
- }
- int Gauss()
- {
- int k,col;
- for(k=0,col=0;k<equ&&col<var;k++,col++){
- int mx=k;
- for(int i=k+1;i<equ;i++)
- if(a[i][col]>a[mx][col]) mx=i;
- for(int i=col;i<var+1;i++)
- swap(a[k][i],a[mx][i]);
- if(!a[k][col]){
- k--;
- free_x[free_num++]=col;
- continue;
- }
- for(int i=k+1;i<equ;i++){
- if(a[i][col]){
- for(int j=col;j<var+1;j++)
- a[i][j]^=a[k][j];
- }
- }
- }
- for(int i=k;i<equ;i++)
- if(a[i][col]) return -1;
- return var-k;
- }
- int calu()
- {
- int t=Gauss();
- if(t==-1) return -1;
- int ans;
- if(t==0){
- ans=0;
- for(int i=var-1;i>=0;i--){
- x[i]=a[i][var];
- for(int j=i+1;j<var;j++)
- x[i]^=(x[j]&&a[i][j]);
- ans+=x[i];
- }
- }
- else{
- ans=10000000;
- for(int i=0;i<(1<<t);i++){
- int tmp=0;
- for(int j=0;j<t;j++){
- if(i&(1<<j)){
- x[free_x[j]]=1;
- tmp++;
- }
- else
- x[free_x[j]]=0;
- }
- for(int j=var-t-1,k;j>=0;j--){
- for(k=j;k<var;k++)
- if(a[j][k]) break;
- x[k]=a[j][var];
- for(int l=k+1;l<var;l++)
- x[k]^=(a[j][l]&&x[l]);
- tmp+=x[k];
- }
- ans=min(ans,tmp);
- }
- }
- return ans;
- }
- int main()
- {
- while(~scanf("%d",&s[0])){
- for(int i=1;i<20;i++)
- scanf("%d",&s[i]);
- init();
- cout<<calu()<<endl;
- }
- return 0;
- }
POJ 2965 http://poj.org/problem?id=2965
AX=B => X=A^(-1)*B 通过逆矩阵来求X,当然这题也能够打表 把A的逆矩阵给打出来 后面来一组数据乘一次 效率非常高
[cpp] view plaincopy
- #include <iostream>
- #include <cstring>
- #include <cstdio>
- using namespace std;
- int a[16][33];
- int free_x[16],equ,var;
- int c[16][16];
- /*int c[16][16]={
- 1, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0,
- 1, 1, 1, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0,
- 1, 1, 1, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0,
- 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1,
- 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0,
- 0, 1, 0, 0, 1, 1, 1, 1, 0, 1, 0, 0, 0, 1, 0, 0,
- 0, 0, 1, 0, 1, 1, 1, 1, 0, 0, 1, 0, 0, 0, 1, 0,
- 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1,
- 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0,
- 0, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 0, 1, 0, 0,
- 0, 0, 1, 0, 0, 0, 1, 0, 1, 1, 1, 1, 0, 0, 1, 0,
- 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1,
- 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1,
- 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1,
- 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 1, 1, 1,
- 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1
- };*/
- void init()
- {
- memset(a,0,sizeof(a));
- int k=0;
- for(int i=0;i<4;i++){
- for(int j=0;j<4;j++){
- k=i*4+j;
- for(int p=0;p<4;p++){
- a[k][i*4+p]=1;
- a[k][p*4+j]=1;
- }
- }
- }
- for(int i=0;i<16;i++) a[i][i+16]=1;
- }
- void gauss()
- {
- for(int i=0;i<16;i++){
- int k;
- for(k=i;k<16;k++)
- if(a[k][i]) break;
- for(int j=0;j<32;j++) swap(a[i][j],a[k][j]);
- for(int j=0;j<16;j++){
- if(i!=j&&a[j][i]){
- for(int k=0;k<32;k++)
- a[j][k]=a[j][k]^a[i][k];
- }
- }
- }
- for(int i=0;i<16;i++)
- for(int j=0;j<16;j++)
- c[i][j]=a[i][j+16];
- }
- int main()
- {
- char mp[10];
- int b[16];
- memset(b,0,sizeof(b));
- for(int i=0;i<4;i++){
- cin>>mp;
- for(int j=0;j<4;j++){
- if(mp[j]==‘+‘)
- b[i*4+j]=1;
- }
- }
- init();
- gauss();
- /*for(int i=0;i<16;i++){
- for(int j=0;j<16;j++)
- cout<<c[i][j]<<",";
- cout<<endl;
- }*/
- int ans[16];
- int sum=0;
- memset(ans,0,sizeof(ans));
- for(int i=0;i<16;i++){
- for(int j=0;j<16;j++)
- ans[i]=ans[i]^(c[i][j]&&b[j]);
- sum+=ans[i];
- }
- cout<<sum<<endl;
- for(int i=0;i<16;i++){
- if(ans[i]==1)
- cout<<i/4+1<<" "<<i%4+1<<endl;
- }
- return 0;
- }
高斯消元学习
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。