Pagini recente » Cod sursa (job #2211037) | Cod sursa (job #2697556) | Cod sursa (job #630433) | Cod sursa (job #3184331) | Cod sursa (job #2061298)
#include <vector>
#include <algorithm>
#include <fstream>
using namespace std;
struct SumEntry{
SumEntry(int val, int index) : m_Value(val), m_Index(index){}
int m_Value;
int m_Index;
};
bool CompareSumEntry(const SumEntry& a, const SumEntry& b)
{
return a.m_Value < b.m_Value;
}
int ExtraWeightRemoveColumn(const vector<vector<short>>& matrix, const vector<SumEntry>& columns, const vector<SumEntry>& rows, int index, int rowsToBeRemoved)
{
vector<SumEntry> newRows(rows);
for(int i = 0; i < newRows.size(); i++)
{
newRows[i].m_Value -= matrix[i][index];
}
sort(newRows.begin(), newRows.end(), CompareSumEntry);
int sum = 0;
for(int i = 0; i < rowsToBeRemoved; i++)
{
sum += newRows[i].m_Value;
}
return sum;
}
void RemoveColumn(const vector<vector<short>>& matrix, vector<SumEntry>& columns, vector<SumEntry>& rows, int index)
{
for(int i = 0; i < rows.size(); i++)
{
rows[i].m_Value -= matrix[i][index];
}
columns.erase(columns.begin() + index);
}
int main()
{
vector<vector<short>> matrix;
int m, n, r, c;
ifstream f("elimin.in");
ofstream g("elimin.out");
f >> m >> n >> r >> c;
for(int i = 0; i < m; i++)
{
matrix.push_back(vector<short>());
for(int j = 0; j < n; j++)
{
short x;
f >> x;
matrix[i].push_back(x);
}
}
vector<SumEntry> columnSum(n, SumEntry(0, 0));
vector<SumEntry> rowSum(m, SumEntry(0, 0));
for(int i = 0; i < m; i++)
{
for(int j = 0; j < n; j++)
{
columnSum[j].m_Value += matrix[i][j];
rowSum[i].m_Value += matrix[i][j];
columnSum[j].m_Index = j;
rowSum[i].m_Index = i;
}
}
for(int i = 0; i < c; i++)
{
int minIndex = 0;
int min = 0x3f3f3f3f;
for(int j = 0; j < columnSum.size(); j++)
{
int sum = columnSum[j].m_Value + ExtraWeightRemoveColumn(matrix, columnSum, rowSum, columnSum[j].m_Index, r);
if(min > sum)
{
min = sum;
minIndex = columnSum[j].m_Index;
}
}
RemoveColumn(matrix, columnSum, rowSum, minIndex);
}
sort(rowSum.begin(), rowSum.end(), CompareSumEntry);
int sum = 0;
for(int i = r; i < m; i++)
{
sum += rowSum[i].m_Value;
}
g << sum;
}