#include using namespace std; using ll = long long; struct edge{ int to; ll cap; int rev; }; //Dinic(0-indexed) struct MaxFlow{ private: static const ll INF=9e18; vector dist, iter; vector> idx; void bfs(int s){ int from; fill(dist.begin(), dist.end(), -1); queue que; que.push(s); dist[s] = 0; while(!que.empty()){ from = que.front(); que.pop(); for (auto &e : E[from]){ if (e.cap > 0 && dist[e.to] == -1){ dist[e.to] = dist[from] + 1; que.push(e.to); } } } } ll dfs(int s, int t, ll flow){ if (s == t) return flow; for (int &i=iter[s]; i= dist[e.to]) continue; ll d = dfs(e.to, t, min(flow, e.cap)); if (d > 0){ e.cap -= d; E[e.to][e.rev].cap += d; return d; } } return 0; } public: int N, M=0; vector> E; MaxFlow(int n) : N(n) { E.resize(N); dist.resize(N); iter.resize(N); } void add_edge(int from, int to, ll cap){ M++; idx.push_back({from, (int)E[from].size()}); E[from].push_back({to, cap, (int)E[to].size()}); E[to].push_back({from, 0, (int)E[from].size()-1}); } ll solve(int s, int t, ll limit=INF){ ll res = 0, flow; while(1){ bfs(s); if (dist[t] == -1) break; for (int i=0; i 0){ res += flow; if (res >= limit) return limit; } } return res; } //i番目の辺の(from, to, flow)を求める。 tuple get_flow(int i){ assert (i < M); edge &e = E[idx[i].first][idx[i].second]; return {idx[i].first, e.to, E[e.to][e.rev].cap}; } //最小カット(s->t)を求める vector> get_cut(int s){ vector vst(N); vector> res; auto dfs=[&](auto self, int from)->void{ vst[from] = 1; for (auto &e : E[from]){ if (vst[e.to]) continue; if (e.cap) self(self, e.to); } }; dfs(dfs, s); for (int i=0; i> N >> S >> T; MaxFlow mf(N+2); for (int i=0; i> x; mf.add_edge(0, x, 1e18); } for (int i=0; i> x; mf.add_edge(x, N+1, 1e18); } for (int i=1; i<=N; i++){ for (int j=1; j<=N; j++){ cin >> C; mf.add_edge(i, j, C); if (i>j) sm += C; } } cout << sm - mf.solve(0, N+1) << endl; return 0; }