[AGC036D] Negative Cycle

题意翻译

**【题意简述】** 有一个 $N$ 个点的有向图，节点标号为 $0 \sim (N - 1)$。 这张图初始时只有 $N - 1$ 条边，每条边从 $i$ 指向 $i + 1$，边权为 $0$。 对于每一对 $i, j$（$0 \le i, j \le N - 1$，$i \ne j$），Snuke 会加入新边 $i \to j$，如果 $i < j$ 则边权为 $-1$，否则边权为 $1$。 Ringo 不喜欢图中的负环，所以他想要删掉一些 Snuke 加入的边，使得最终得到的图没有负环。 但是删掉每一条边是有代价的，具体地说，删掉 $i \to j$ 这条边，要花费 $A_{i, j}$ 的代价。 请问满足图中不存在负环的最小删边代价是多少？ - $3 \le N \le 500$，$1 \le A_{i, j} \le {10}^9$。

题目描述

[problemUrl]: https://atcoder.jp/contests/agc036/tasks/agc036_d $ N $ 頂点からなる重み付き有向グラフがあり、頂点には $ 0 $ から $ N-1 $ までの番号がついています。 最初、このグラフには $ N-1 $ 本の辺があります。 このうち $ i $ 番目 ($ 0\ \leq\ i\ \leq\ N-2 $) の辺は、 頂点 $ i $ から頂点 $ i+1 $ へ向かう重さ $ 0 $ の辺です。 すぬけさんはこれから、全ての $ i,j $ ($ 0\ \leq\ i,j\ \leq\ N-1,\ i\ \neq\ j $) について、新たに辺 $ (i\ →\ j) $ を追加する操作を行います。 辺の重さは、$ i\ <\ j $ なら $ -1 $、そうでないなら $ 1 $ とします。 りんごくんは、グラフに負閉路（閉路であって、そこに含まれる辺の重みの総和が $ 0 $ 未満のもの）があるととても悲しいです。 そこで、すぬけさんが追加した辺のうちいくつかを削除して、最終的なグラフに負閉路が含まれないようにすることにしました。 すぬけさんが追加した辺 $ (i\ →\ j) $ を削除するには $ A_{i,j} $ のコストがかかります。 なお、最初からあった $ N-1 $ 本の辺を削除することはできません。 りんごくんが目的を達成するために必要なコストの総和の最小値を求めてください。

输入输出格式

输入格式


入力は以下の形式で標準入力から与えられる。 > $ N $ $ A_{0,1} $ $ A_{0,2} $ $ A_{0,3} $ $ \cdots $ $ A_{0,N-1} $ $ A_{1,0} $ $ A_{1,2} $ $ A_{1,3} $ $ \cdots $ $ A_{1,N-1} $ $ A_{2,0} $ $ A_{2,1} $ $ A_{2,3} $ $ \cdots $ $ A_{2,N-1} $ $ \vdots $ $ A_{N-1,0} $ $ A_{N-1,1} $ $ A_{N-1,2} $ $ \cdots $ $ A_{N-1,N-2} $

输出格式


りんごくんが目的を達成するために必要なコストの総和の最小値を出力せよ。

输入输出样例

输入样例 #1

3
2 1
1 4
3 3

输出样例 #1

2

输入样例 #2

4
1 1 1
1 1 1
1 1 1
1 1 1

输出样例 #2

2

输入样例 #3

10
190587 2038070 142162180 88207341 215145790 38 2 5 20
32047998 21426 4177178 52 734621629 2596 102224223 5 1864
41 481241221 1518272 51 772 146 8805349 3243297 449
918151 126080576 5186563 46354 6646 491776 5750138 2897 161
3656 7551068 2919714 43035419 495 3408 26 3317 2698
455357 3 12 1857 5459 7870 4123856 2402 258
3 25700 16191 102120 971821039 52375 40449 20548149 16186673
2 16 130300357 18 6574485 29175 179 1693 2681
99 833 131 2 414045824 57357 56 302669472 95
8408 7 1266941 60620177 129747 41382505 38966 187 5151064

输出样例 #3

2280211

说明

### 制約 - $ 3\ \leq\ N\ \leq\ 500 $ - $ 1\ \leq\ A_{i,j}\ \leq\ 10^9 $ - 入力される値はすべて整数である。 ### Sample Explanation 1 すぬけさんが追加した辺 $ (0\ →\ 1) $ を削除すると、グラフに負閉路がないようになります。 この時必要なコストは $ 2 $ で、これが最小です。 ### Sample Explanation 2 すぬけさんが追加した辺 $ (1\ →\ 2) $ と $ (3\ →\ 0) $ を削除すると、グラフに負閉路がないようになります。 この時必要なコストは $ 1+1=2 $ で、これが最小です。