/* FILE: minCoverWithTowers.cpp last change: 2-Jul-2014 author: Romeo Rizzi * linear O(n^2) time and O(n) memory solution based on the observation that any feasible solution: * either places at least one tower on each row; * or places at least one tower on each column. */ #define NDEBUG // NDEBUG definita nella versione che consegno #include #ifndef NDEBUG # include // uso di cin e cout non consentito in versione finale #endif #include using namespace std; const int MAX_COST = 10000; const int MAX_N = 1000; int n; int minCostOnRow[MAX_N], minCostOnCol[MAX_N], numMinOnRow[MAX_N], numMinOnCol[MAX_N]; int myMin( int a, int b ) { return (a> n; for(int i = 0; i < n; i++) minCostOnRow[i] = minCostOnCol[i] = MAX_COST; for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) { int tmp; fin >> tmp; minCostOnRow[i] = myMin(minCostOnRow[i], tmp); minCostOnCol[j] = myMin(minCostOnCol[j], tmp); } fin.close(); int costRow, costCol; costRow = costCol = 0; for(int i = 0; i < n; i++) { costRow += minCostOnRow[i]; // cout << minCostOnRow[i] << " "; costCol += minCostOnCol[i]; // cout << minCostOnCol[i] << " "; } ofstream fout("output.txt"); assert( fout ); fout << myMin( costRow, costCol ) << endl; fout.close(); return 0; }