Pagini recente » Cod sursa (job #2391581) | Cod sursa (job #2356842) | Cod sursa (job #2679584) | Cod sursa (job #2548199) | Cod sursa (job #976294)
Cod sursa(job #976294)
#include <iostream>
#include <fstream>
#include <vector>
#define MAX_POSSIBLE 2147483647
using namespace std;
vector< vector<short> > mat;
vector<bool> eliminln;
vector<bool> eliminclmn;
vector<short> temp_ln;
vector<short> temp_clmn;
short m,n,R,C,a;
int result,result_max=0;
long minclmn=MAX_POSSIBLE;
int sum_clmn(short z)
{
long s=0;
for(short i=0;i<m;i++)
s+=mat[i][z];
return s;
}
void elimin_ln(short sz)
{
for(short i=0;i<n;i++)
mat[sz][i]=0;
eliminln[sz]=true;
}
void elimin_clmn(short h)
{
for(short i=0;i<m;i++)
mat[i][h]=0;
eliminclmn[h]=true;
}
int min_clmn()
{
short p;
long d;
for(short i=0;i<n;i++)
{
d=sum_clmn(i);
if(d<minclmn && eliminclmn[i]!=true)
{
p=i;
minclmn=d;
}
}
return p;
}
int sum()
{
long b=0;
for(short i=0;i<m;i++)
for(short j=0;j<n;j++)
b+=mat[i][j];
return b;
}
void backt_ln(short k)
{
if(k>R)
{
for(short l=0;l<C;l++)
{
a=min_clmn();
if(eliminclmn[a]!=true)
{
for(short p=0;p<m;p++)
temp_clmn[p]=mat[p][a];
elimin_clmn(a);
}
}
result=sum();
if(result>result_max)
result_max=result;
}
else
for(short i=0;i<m;i++)
if(eliminln[i]!=true)
{
for(short j=0;j<n;j++)
temp_ln[j]=mat[i][j];
elimin_ln(i);
a=min_clmn();
backt_ln(k+1);
for(short p=0;p<m;p++)
mat[p][a]=temp_clmn[p];
for(short j=0;j<n;j++)
mat[i][j]=temp_ln[j];
}
}
int main()
{
ifstream f("elimin.in");
ofstream g("elimin.out");
f>>m>>n>>R>>C;
mat.resize(m);
for(short i=0;i<m;i++)
mat[i].resize(n);
for(short i=0;i<m;i++)
for(short j=0;j<n;j++)
f>>mat[i][j];
eliminln.resize(m);
eliminclmn.resize(n);
temp_ln.resize(n);
temp_clmn.resize(m);
backt_ln(1);
g<<result_max;
cout<<result_max;
}