include map include cstdio include iostream include iomanip include st

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
#include <map>
#include <cstdio>
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <cmath>
#include <cstring>
#include <climits>
#include <algorithm>
#include <functional>
#include <set>
#include <queue>
#include <ctime>
using namespace std;
typedef pair<int, int> PII;
#define PATH "D:\\QtProjects\\olymp\\"
#define forn(i, n) for (int i = 0; i < (n); ++i)
const int N = 1000;
const int M = 1000000;
const int inf = (int)1e9;
int head[N], phi[N], dist[N], predArc[N];
int link[M], dest[M], cap[M], cost[M];
int S, T;
int arcsCnt = 0;
inline void init(){
fill(head, head + N, -1);
}
inline void add_arc(int from, int to, int ccap, int ccost){
cap[arcsCnt] = ccap;
cost[arcsCnt] = ccost;
dest[arcsCnt] = to;
link[arcsCnt] = head[from];
head[from] = arcsCnt++;
}
inline void add_edge(int from, int to, int capacity, int cost){
add_arc(from, to, capacity, cost);
add_arc(to, from, 0, -cost);
}
bool used[N];
priority_queue<PII, vector<PII>, greater<PII> > q;
inline int dejkstra(){
fill(used, used + T + 1, false);
fill(dist, dist + T + 1, inf);
dist[S] = 0;
q.emplace(0, S);
while (!q.empty()){
// cout << q.size() << endl;
int v = q.top().second;
q.pop();
if (used[v]) continue;
used[v] = true;
for (int arc = head[v]; arc != -1; arc = link[arc]){
if (cap[arc] == 0) continue;
int u = dest[arc];
int d = dist[v] + (phi[v] - phi[u]) + cost[arc];
if (d < dist[u]){
q.emplace(d, u);
dist[u] = d;
predArc[u] = arc;
}
}
}
return dist[T] + phi[T];
}
inline int mcmf(){
int ans = 0;
int pushed = 0;
while (true){
int ccost = dejkstra();
if (dist[T] == inf) break;
int mincap = inf;
for (int v = T; v != S; v = dest[predArc[v] ^ 1]){
mincap = min(mincap, cap[predArc[v]]);
}
for (int v = T; v != S; v = dest[predArc[v] ^ 1]){
cap[predArc[v]] -= mincap;
cap[predArc[v] ^ 1] += mincap;
}
for (int i = 0; i <= T; ++i)
if (dist[i] != inf)
phi[i] += dist[i];
pushed += mincap;
ans += mincap * ccost;
}
// cout << "pushed = " << pushed << endl;
return ans;
}
int a[300][300];
int sum[301];
int main(){
// freopen(PATH"input.txt", "r", stdin);
ios_base::sync_with_stdio();
init();
int n; cin >> n;
S = 2 * n;
T = S + 1;
for (int i = 0; i < n; ++i){
for (int j = 0; j < n; ++j){
cin >> a[i][j];
sum[j] += a[i][j];
}
add_edge(S, i, 1, 0);
add_edge(n + i, T, 1, 0);
}
for (int i = 0; i < n; ++i){
for (int j = 0; j < n; ++j){
int cost = sum[i] - a[j][i];
// cout << cost << ' ';
add_edge(i, n + j, 1, cost);
}
// cout << endl;
}
cout << mcmf() << endl;
return 0;
}