Pagini recente » Cod sursa (job #2271278) | Cod sursa (job #1636332) | Cod sursa (job #2218232) | Cod sursa (job #1118371) | Cod sursa (job #913525)
Cod sursa(job #913525)
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("flip.in");
ofstream g("flip.out");
int a[17][17],N,M,lp[17],ln[17],cn[17],cp[17];
int linsch()//care linie ar putea fi schimbata
{
int l=0,i;
int dl=0;
for(i=1;i<=N;i++)
if((-1)*ln[i]>lp[i] && (-ln[i]-lp[i])>dl)
{
l=i;
dl=-ln[i]-lp[i];
}
//cout<<"#"<<dl<<"#";
return l;
}
int colsch()//care coloana ar putea fi schimbata
{
int l=0,i;
int dl=0;
for(i=1;i<=M;i++)
if((-1)*cn[i]>cp[i] && (-1)*cn[i]-cp[i]>dl)
{
l=i;
dl=(-1)*cn[i]-cp[i];
}
return l;
}
void schlin(int i)
{
int j;
for(j=1;j<=M;j++)
a[i][j]=a[i][j]*(-1);
}
void schcol(int i)
{
int j;
for(j=1;j<=N;j++)
a[j][i]=a[j][i]*(-1);
}
int main()
{
int i,j,l,c,ok,aux;
f>>N>>M;
for(i=1;i<=N;i++)
for(j=1;j<=M;j++)
{
f>>a[i][j];
if(a[i][j]>0)
{
lp[i]+=a[i][j];
cp[j]+=a[i][j];
}
else
{
ln[i]+=a[i][j];
cn[j]+=a[i][j];
}
}
do
{
ok=1;
l=colsch();
if(l>0)
{
ok=0;
schcol(l);
aux=cn[l];
cn[l]=cp[l];
cp[l]=aux;
cn[l]=-cn[l];
cp[l]=-cp[l];
for(j=1;j<=N;j++)
if(a[j][l])
{
ln[j]+=a[j][l];
lp[j]+=a[j][l];
}
else
{
ln[j]-=a[j][l];
lp[j]-=a[j][l];
}
}
l=linsch();
if(l>0)
{
ok=0;
schlin(l);
aux=ln[l];
ln[l]=lp[l];
lp[l]=aux;
ln[l]=-ln[l];
lp[l]=-lp[l];
for(j=1;j<=M;j++)
if(a[l][j])
{
cn[j]+=a[l][j];
cp[j]+=a[l][j];
}
else
{
cn[j]-=a[l][j];
cp[j]-=a[l][j];
}
}
}
while(!ok);
/*for(i=1;i<=N;i++)
{
for(j=1;j<=M;j++)
g<<a[i][j]<<" ";
g<<"\n";
}*/
int s=0;
for(i=1;i<=N;i++)
s+=(lp[i]+ln[i]);
g<<s<<"\n";
g.close();
f.close();
g.close();
return 0;
}