Topic link

Chinese questions , Change the template structure, you can pass , The data is a little bit watery , But you still need free argument enumeration .

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
#include <map>
#include <ctime>
using namespace std;
const int maxn=;
// Yes equ An equation ,var Variables . The number of rows of the augmented matrix is equ, The number of columns is var+1, Respectively 0 To var
int equ,var;
int a[maxn][maxn]; // Augmented matrix
int x[maxn]; // Solution set
int free_x[maxn];// To store free variables ( Multi solution enumeration of free variables can be used )
int free_num;// The number of free variables
// The return value is -1 There is no solution , by 0 It's the only solution , Otherwise, the number of free variables is returned
int gauss()
{
int max_r,col,k;
free_num=;
for(k=,col=; k<equ&&col<var; k++,col++)
{
max_r=k;
for(int i=k+; i<equ; i++)
if(abs(a[i][col])>abs(a[max_r][col]))
max_r=i;
if(!a[max_r][col])
{
k--;
free_x[free_num++]=col;
continue;
}
if(max_r!=k)
for(int j=col; j<var+; j++)
swap(a[k][j],a[max_r][j]);
for(int i=k+; i<equ; i++)
{
if(a[i][col])
{
for(int j=col; j<var+; j++)
a[i][j]^=a[k][j];
}
}
}
for(int i=k; i<equ; i++)
if(a[i][col])
return -;
if(k<var) return var-k;
for(int i=var-; i>=; i--)
{
x[i]=a[i][var];
for(int j=i+; j<var; j++)
x[i]^=(a[i][j]&&x[j]);
}
return ;
}
int n,m;
void init()
{
memset(a,,sizeof(a));
memset(x,,sizeof(x));
equ=n*m;
var=n*m;
for(int i=; i<n; i++)
for(int j=; j<m; j++)
{
int t=i*m+j;
a[t][t]=;
if(i>) a[(i-)*m+j][t]=;
if(i<n-) a[(i+)*m+j][t]=;
if(j>) a[i*m+j-][t]=;
if(j<m-) a[i*m+j+][t]=;
if(i>&&j>) a[(i-)*m+j-][t]=;
if(i>&&j<m-) a[(i-)*m+j+][t]=;
if(i<n-&&j>) a[(i+)*m+j-][t]=;
if(i<n-&&j<m-) a[(i+)*m+j+][t]=;
}
}
int solve()
{
int t=gauss();
if(t==-)
{
return -;
}
else if(t==)
{
int ans=;
for(int i=; i<n*m; i++)
ans+=x[i];
return ans;
}
else
{
// Enumerate free variables
int ans=0x3f3f3f3f;
int tot=(<<t);
for(int i=; i<tot; i++)
{
int cnt=;
for(int j=; j<t; j++)
{
if(i&(<<j)) // Notice that it's not &&
{
x[free_x[j]]=;
cnt++;
}
else x[free_x[j]]=;
}
for(int j=var-t-; j>=; j--)
{
int idx;
for(idx=j; idx<var; idx++)
if(a[j][idx])
break;
x[idx]=a[j][var];
for(int l=idx+; l<var; l++)
if(a[j][l])
x[idx]^=x[l];
cnt+=x[idx];
}
ans=min(ans,cnt);
}
return ans;
}
}
int main()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
init();
for(int i=;i<n;i++)
for(int j=;j<m;j++)
{
cin>>a[i*m+j][n*m];
}
int ans=solve();
if(ans==-)
puts("no sovle!");
else
printf("%d\n",ans);
}
return ;
}

NEFU 505 Super red and black ( Gauss elimination ) More articles about

  1. NEFU 503 Matrix solving ( Not 01 Gauss elimination of XOR )

    Topic link Chinese questions , Gauss elimination template problem . #include <iostream> #include <cstdio> #include <cmath> #include ...

  2. 【 Gauss elimination 】BZOJ3503 [Cqoi2014] Harmony matrix

    3503: [Cqoi2014] Harmony matrix Time Limit: 10 Sec  Memory Limit: 128 MBSec  Special JudgeSubmit: 1197  Solved: ...

  3. P3265 [JLOI2015] Equipment purchase ( Gauss elimination + greedy , linear algebra )

    The question ; Yes n A piece of equipment , Every outfit has m Attributes , The value of each piece of equipment is cost. The little elder brother , To save money , If the first j The attributes of a piece of equipment can be combined from other preparations . such as Each equipment attribute is expressed as , b1, b2.......bm . It can be made by ...

  4. [JLOI2015] Equipment purchase ( Gauss elimination )

    [JLOI2015] Equipment purchase \(solution:\) First of all, the problem surface of this problem has clearly told us that this is a problem of Gaussian elimination in linear space ( One piece of equipment can be used to represent another , It can't be more obvious ), It's just that this question requires us to ...

  5. HihoCoder 1195 Gauss elimination &#183; One ( Gauss elimination )

    The question https://hihocoder.com/problemset/problem/1195 Ideas Gauss elimination is an algorithm for solving high-order equations , Complexity \(O(n^3)\) . The process is roughly : Construct an unknown number ...

  6. BZOJ.3143.[HNOI2013] wander ( probability expect Gauss elimination )

    Topic link Reference resources The song of voyage Multiply the probability of each side by the assigned label is its expectation , So we must assign a large number to the side with the lowest probability of going . We just need to calculate the probability of passing through all the points , You can get through an edge (\(u->v\)) Of ...

  7. 2018.09.23 bzoj3143: [Hnoi2013] wander (dp+ Gauss elimination )

    Portal Obviously, we just need to find out the expected number of times all the edges are passed through , Then greedy put the edge power small edge Dingcheng big number . So how to find out the expected number of times all edges are passed through ? Obviously it's only about the two points where the edges connect . So we just need to find out the expected number of times two points are passed through . about ...

  8. 【BZOJ3143】【HNOI2013】 wander Gauss elimination

    Subject portal :http://www.lydsy.com/JudgeOnline/problem.php?id=3143 We make $P_i$ Says from the first i The expected number of departures from point No . be $P_n$ Obviously $0$. about $P ...

  9. BZOJ3143 [Hnoi2013] wander 【 Gauss elimination 】

    subject An undirected connected graph , Vertex from 1 Number to N, Side from 1 Number to M. Small Z Random walk on this graph , It's small in the beginning Z stay 1 Vertex number , Every step is small Z Randomly choose... With equal probability Select an edge of the current vertex , Go along this edge to the next vertex , Get a braid equal to this side ...

Random recommendation

  1. Schema constraint

    Schema constraint (*xml How to introduce schema constraint )( understand Schema: According to Schema Write XML Document to :)1.Schema The constraint document itself is a XML file .2.Schema Good for namespace support 3.S ...

  2. Moqui Code analysis of learning mantle priceServices.xml

    <?xml version="1.0" encoding="UTF-8"?> <!-- This software is in the pub ...

  3. Ubuntu Can't shut down the solution

    explain : If not, please refer to the last part of the article , Maybe it will help . It's not just ubuntu Inside ,fedora I also encountered this problem , The computer can be restarted , But it can't be turned off directly , Otherwise, it will stop at the shutdown interface all the time , It needs to be shut down manually . It's depressing ...

  4. Finding a needle in Haystack: Facebook’s photo storage

    http://www.importnew.com/3292.html Object oriented storage system

  5. Java Timing task processing scheme under multi machine deployment (mysql)

    Because I have csdn And blog Garden two blogs , So it's going to be done on both sides . csdn Address : http://blog.csdn.net/u012881584/article/details/70194237 Today, let's talk about ...

  6. Java The sixth wave of written interview questions ( Revised version )

    Reprinted to :http://blog.csdn.net/shakespeare001/article/details/51330745 author : Yamadai King ( Happy Yang ) This series arranges Java Related written interview knowledge , Others ...

  7. validator js Validator

    from :https://github.com/jaywcjlove/validator.js Lightweight JavaScript Form validation , String validation . No dependence , Support UMD Import js library <script t ...

  8. Chapter two HTML,JavaScript brief introduction

    Concept : URL: The address of the standard online resource . HTTP agreement : Standard protocol for clients to send requests and get responses . HTML: Hypertext markup language . It's a common language on the Internet , It's also the Internet web Language foundation . 2.1 Server and browser for instance :A classmate ...

  9. Presto Study

    Presto Basic knowledge and concept learning can refer to these blogs : presto 0.166 summary https://www.cnblogs.com/sorco/p/7060166.html Presto Study -prest ...

  10. Java Use Log4 Log

    We are using the system , For the convenience of finding problems , So you need to log the operation , At present, the more mature and stable way of program logging is Log4, I am also a rookie , And then, in the study, you can record the way you use it , For future reference , At the same time, this article refers to the blog Park : ...