Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
Re:高斯消元法~In Reply To:高斯消元法~ Posted by:uptothewind at 2014-06-30 12:39:59 > #include<iostream> > #include<string.h> > #define NUM 4*i+j > #define INF 100000 > using namespace std; > char str[5][6]; > int A[20][20]; > int x[20]; > int Y[20]; > int Major[20]; > int y; > void init() > { > memset(A,0,sizeof(A)); > for(int i=0;i<4;i++) > { > for(int j=0;j<4;j++) > { > for(int k=0;k<=3;k++) > { > if(NUM+k*4<16)A[NUM+k*4][NUM]=1; > if(NUM-k*4>=0)A[NUM-k*4][NUM]=1; > if(NUM+k<=4*i+3)A[NUM+k][NUM]=1; > if(NUM-k>=4*i)A[NUM-k][NUM]=1; > } > if(str[i][j]=='+')A[NUM][16]=1; > } > > } > } > int dfs_fr(int row,int var) > { > if(row==-1||var==-1) > { > int sum=0; > for(int i=0;i<16;i++) > sum+=x[i]; > if(sum<y) > { > for(int i=0;i<16;i++)Y[i]=x[i]; > y=sum; > } > return y; > } > if(var==Major[row]) > { > int sum=A[row][16]; > for(int j=var+1;j<16;j++) > { > if(A[row][j]==0)continue; > sum^=x[j]; > } > x[var]=sum; > dfs_fr(row-1,var-1); > } > else > { > for(int i=0;i<2;i++) > { > x[var]=i; > dfs_fr(row,var-1); > } > } > return y; > } > int Gauss() > { > int r,c; > for(r=0,c=0;r<16&&c<16;r++,c++) > { > int max_r=r; > for(int i=r+1;i<16&&!A[r][c];i++) > { > if(A[i][c]>A[r][c]){max_r=i;break;} > } > if(max_r!=r) > { > for(int j=0;j<=16;j++) > swap(A[max_r][j],A[r][j]); > } > if(A[r][c]==0){r--;continue;} > for(int i=r+1;i<16;i++) > { > if(A[i][c]==0)continue; > for(int j=c;j<=16;j++) > { > A[i][j]^=A[r][j]; > } > } > Major[r]=c; > } > y=INF; > return dfs_fr(r-1,c-1); > } > > int main() > { > > while(cin>>str[0]) > { > for(int i=1;i<4;i++)cin>>str[i]; > init(); > int ans=Gauss(); > cout<<ans<<endl; > for(int i=0;i<16;i++) > if(Y[i])cout<<i/4+1<<" "<<i%4+1<<endl; > } > return 0; > } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator