0a47836e.cpp

#include <bits/stdc++.h>
#define alive std::cout << "$LINE @" << __LINE__ << " ALIVE" << std::endl
#define watch(var) std::cout << "$ LINE @" << __LINE__ << " FUN @" << __FUNCTION__ \
                             << " VAR @" << (#var) << ": " << (var) << std::endl

using namespace std;

typedef int i32;
typedef unsigned int u32;
typedef long long i64;
typedef unsigned long long u64;
typedef double f64;
typedef long double f128;
typedef pair<int, int> pii;

template <typename Tp>
inline void read(Tp &x)
{
    x = 0;
    bool neg = false;
    char c = getchar();
    for (; !isdigit(c); c = getchar())
    {
        if (c == '-')
        {
            neg = true;
        }
    }
    for (; isdigit(c); c = getchar())
    {
        x = x * 10 + c - '0';
    }
    if (neg)
    {
        x = -x;
    }
}

const int N = 100 + 5;
const int M = N * 2;
const int K = 1e5 + 5;
const int INF = 0x3f3f3f3f;

int n, k, S, T;

int head[M], E = 1;
struct Edge
{
    int to, next, flow, cost;
} e[K];
inline void addEdge(const int &u, const int &v, const int &flow, const int &cost)
{
    e[++E] = (Edge){v, head[u], flow, cost};
    head[u] = E;
}
inline void addE(const int &u, const int &v, const int &flow, const int &cost)
{
    addEdge(u, v, flow, cost);
    addEdge(v, u, 0, -cost);
}

int dis[M], parE[M], parV[M];
bool inQ[M];

inline bool bfs()
{
    memset(dis, 0x3f, sizeof(dis));
    memset(inQ, 0, sizeof(inQ));

    dis[S] = 0;

    queue<int> q;
    q.emplace(S);

    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        inQ[u] = false;

        for (int i = head[u], v; v = e[i].to, i; i = e[i].next)
        {
            if (e[i].flow && dis[v] > dis[u] + e[i].cost)
            {
                dis[v] = dis[u] + e[i].cost;
                parE[v] = i;
                parV[v] = u;
                if (!inQ[v])
                {
                    q.emplace(v);
                    inQ[v] = true;
                }
            }
        }
    }

    return dis[T] < INF;
}

#define IN(x) ((x) << 1)
#define OUT(x) ((x) << 1 | 1)

int main()
{
    read(n), read(k);

    S = n * 2 + 4, T = n * 2 + 5;
    for (int i = 2; i <= n + 1; ++i)
    {
        addE(S, OUT(i), 1, 0);
        addE(IN(i), T, 1, 0);
        addE(OUT(i), IN(1), k, 0);
    }
    addE(IN(1), OUT(1), k, 0);
    for (int i = 1, dis; i <= n; ++i)
    {
        for (int j = i + 1; j <= n + 1; ++j)
        {
            read(dis);
            addE(OUT(i), IN(j), INF, dis);
        }
    }

    int ans = 0;

    while (bfs())
    {
        int flow = INF;
        for (int cur = T; cur != S; cur = parV[cur])
        {
            flow = std::min(flow, e[parE[cur]].flow);
        }
        ans += flow * dis[T];
        for (int cur = T; cur != S; cur = parV[cur])
        {
            e[parE[cur]].flow -= flow;
            e[parE[cur] ^ 1].flow += flow;
        }
    }

    printf("%d\n", ans);

    return 0;
}

#undef IN
#undef OUT