Ada and Banquet

#include <bits/stdc++.h>

using namespace std;

#define long long long int

int N;
vector<vector<int>> A;

int min_cut() {
    int ans = INT_MAX;
    for (int i = 1; i < N; i++) {
        vector<int> w(N, 0);
        vector<bool> vis(N, false);

        int prev = -1, v = 0, cnt = 1, cut;
        while (cnt <= N - i) {
            vis[v] = true;
            int nxt = -1;
            cut = 0;

            for (int j = 0; j < N; j++) {
                w[j] += A[v][j];
                if (!vis[j] && w[j] > cut)
                    nxt = j, cut = w[j];
            }

            cnt++;
            prev = v;
            v = nxt;
        }

        ans = min(ans, cut);
        for (int j = 0; j < N; j++) {
            if (j != prev) {
                A[j][prev] += A[j][v];
                A[prev][j] += A[v][j];
            }

            A[j][v] = 0;
        }
    }

    return ans;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> N;

    A.assign(N, vector<int>(N));
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            cin >> A[i][j];

    int ans = 2 * min_cut();
    cout << ans << "\n";
}