2022-06-08

感想：COCI COI 2022 (Croatian Olympiad in Informatics 2022.)

Croatian Olympiad in Informatics (COI) 2022 - Codeforces
2022年5月30日にCOCIの最終ラウンド (COI) があった。Openコンテストに参加した。非公式解答を書いておく。

COCIについて

COI は IOI のクロアチア大会および代表選考の大会である。COI はクロアチアの中学生高校生のための大会だがオープンコンテストが COCI で開かれており、無関係の人も COI の問題に挑戦することができる。

コンテストまとめ

	ジャンル	難易度
問1	インタラクティブ、基礎よりの知識問題	易
問2	IOIコミュニケーション	難
問3	グラフ	難
問4	木グラフ、データ構造	普通

問1：Mađioničar

問題

インタラクティブの問題である。ジャッジは長さ N の文字列を持っている。あなたは次の質問を最大 2×N 回行うことができる。

質問 query(i, j)：文字列の i 番目から j 番目の部分文字列 (連続、両端を含む) が回文ならば 1 を返答する、回文でないならば 0 を返答する

ジャッジが持っている文字列の部分文字列の中で最長の回文の長さは何文字であるか求めよ。

解答

回文を線形時間で求める Manacher アルゴリズムを用いる。ほぼ Manacher そのままで文字列の一致の判定部分を質問に置き換えてやればよい。
そのままだと 2N 回の質問の上限を超えてしまう場合は、長さ1の自明な質問や、同じ質問の繰り返しをしないようにしてやればよい。

問2：Mensza

IOIコミュニケーション形式の問題。アイデア勝負のパズル系の問題なのでネタバレ防止の為に別記事に書き記す。
natsugiri.hatenablog.com

問3：Povjerenstvo

問題

N人の人がいる。「人xは人yが嫌い」というような情報が M 個与えられる。N人のうちの何人かを委員会の委員にしたい。ただし、嫌いな人と一緒に委員会を行いたくないので、全ての人は以下の条件を満たさなければならない。

「あいつは委員にしない」：人xが委員であるならば、人xが嫌いな人は一人も委員ではない
「あいつが居るから委員をやらない」：人xが委員でないならば、人xが嫌いな人が少なくとも一人は委員である

入力の制約として、「人xは人yが嫌い」を頂点 x から頂点 y への辺として、N 頂点の有向グラフを作ると奇数頂点のサイクルは存在しないことが保証されている。
条件を満たすような委員会の委員の割り当てを求めよ（複数考えられる場合はどれか一つを求めよ）。割り当てが存在しないならばそれを指摘せよ。
1 ≦ N ≦ 500000
0 ≦ M ≦ 500000

解答

強連結成分分解をする。1つの強連結成分は単一の頂点、もしくは奇数サイクルを持たない、という特徴を持つ。
トポロジカルソートの逆順に貪欲に割り当てを決めていく。N 人全ての人について、委員であるかないか不定の状態からスタートする。各頂点について、

すでに嫌いな人が委員に決まっているならば、委員にしない
すべての嫌いな人が委員ではないと決まっているならば、委員にする

と、後退解析に次々に連鎖して決めていく。連鎖が止まったら、適当な人を委員にしてまた後退解析を継続する。
これでうまくいくが証明ができてない。

問4：Vinjete

問題

木グラフが与えられる。辺を通るときは M 種類のアイテムのうち幾つかを持っている必要があり、辺 i を通るときにはアイテムの番号が L[i] から R[i] までの全てを持っている必要がある。
頂点 1 から頂点 x まで最短パスで移動するときに、いくつのアイテムを持っている必要があるか、全ての x (2 ≦ x ≦ N) について求めよ。

1 ≦ N ≦ 100'000
1 ≦ M ≦ 1000'000'000

解答

DFSをしながら、必要なアイテムをセグツリーでアップデートしていく。各辺を通るときに、各アイテムについて「必要になった回数」を +1 すると「必要になった回数が 0 回」のアイテムを数えることができる。
セグツリーのノードは「x番からy番のアイテムの中で必要になった回数の最小値は c 回、そのようなアイテムは k 個ある」という状態を持つ。c が 0 であるか確認したのちに k が必要にならないアイテムの個数になる。最小値の更新は区間に加算する遅延評価のセグツリーでできる。
M が大きい時は座標圧縮することで 2N+2 以下にすることができる。
このように「区間に加算・区間の 0 の個数」という問題は 0 未満にならないことがわかっているならば「区間に加算・区間の最小値の個数」を解くことで求められる。

2022-04-01

(XIX Open Cup, Grand Prix of Siberia) Problem 11. Recursive Circuit 解法

グラフ

再帰的な構造の迷路。考察が結構面白いので解法は読まない方がいい。

はじめに

2018年11月18日に開催された XIX Open Cup named afer E.V. Pankratiev, Grand Prix of Siberia の問11「Recursive Circuit」の問題と解法を述べる。

Open Cup

Open CupはICPCに似たルールで5時間 10~14問程度の3人以下チームのプログラミングコンテスト。参加が招待制なので、参加したい場合は参加者の誰かに尋ねて日本の管理者を紹介してもらってアカウントを作ってもらうことになる。問題を解きたいだけなら Codeforces (Gym - Codeforces) で一部が利用できる。問題文を読むだけならば List of All Open Cup Contests - Codeforces から閲覧できる。

XIX Open Cup, Grand Prix of Siberia

Open Cupはどこかの大学のプログラミングキャンプなどで出題された問題を再利用する形で出題されることが多いと思う。今回は Siberia。
この XIX Open Cup, Grand Prix of Siberia はGYMに移植されていないので Open Cup アカウントを持っていない人はジャッジが利用できない。問題文は XIX Open Cup. Stage 7. Grand Prix of Siberia.pdf — Яндекс.Диск で閲覧できる。
Recursive Circuit は XIX の中の Stage 7 の中の11問目。

問題

再帰的構造を持つ回路を考える。回路の内部には S 個のサブ回路が配置してある。サブ回路は回路全体と同じ構造をしている、つまり無限に再帰的な構造をした回路になっている（画像はもとの問題文より）。

f:id:natsugiri:20220401030629p:plain — Recursive Circuit

回路は N 個の端子を持つ。

1 から K 番の端子は回路の外部から利用することができる。
a*K + j 番の端子は a 番目のサブ回路の j 番目の外部端子である。
残りの端子はほかの端子を繋ぐための端子である。

いくつかの端子のペアは短絡に繋がっている。
最も外側の回路の外部端子2つを選んで片方からもう片方に信号を流すときに少なくともどれだけの「深さ」まで潜るかを求めたい。深さとは、最も外側の回路の深さが 0。内部の回路の深さは 1。そのさらに内部の回路の深さは 2 ...。

深さを求める Q 個の質問に答えよ。ただし信号が流れない場合は-1を出力せよ。
例えば、(3, 4) と質問された場合、上の画像の3番の端子と4番の端子に信号を流すにはサブ回路のサブ回路を通る必要があるので深さは2。

制約

K * (S+1) <= N <= 100000
M <= 100000
Q <= 100000
他の制約は原文を見る。

解法

2022-02-14

2021年終わり

2021年は1770問を読んで1270問の正解をした。解けなかった問題をほぼ復習しなかった。
それら問題の表を置いておく。ただしテスターとして参加したものは削除しておいた。

コメントを書くのが面倒なのこの形式でメモしているが、ちょっとでもコメントがあると見返したとき面白い。

2022-01-29

「競プロ典型 90 問」解いた感想

典型90問を全て解いた。
競プロ典型 90 問 - AtCoder

詩

年始から初めておよそ3週間やった。典型90問は2021年4月くらいからオンラインジャッジが利用可能だったはずなのでかなり時代遅れになってしまった。
せっかくまとまった教材があるのでやってみよう。

感想

90問は終わりの見える問題量でよい
すべての問題に解説がある。出題されたTwitterの方を見れば問題と解説が図示されていてとても良い。
AtCoderのジャッジで他人のソースコードを見ることができるのがよい
問題が簡単すぎない。AtCoder Beginner Contest (ABC)の問Aや問Bのようなプログラミング言語の確認をするような問題ではなく、一番簡単な問題でも最低限の算数がある
一部の星7レベルの問題はかなり難しい。90問を全て完璧に正解してAtCoder Problemsを緑に埋めたい強迫に駆られる場合は覚悟が要る。

勉強法として全ての問題を漏れなく解くのが理想だが、星7レベルは部分点だけ取って後回しとするのがよさそう。最後の問題の満点解法は ABC の問Exレベルで出題されそうではあるが、ABCを卒業するレート2000を目指すならオーバーなレベル。
公開された当時のABCは6問の問題セットだった。ABC212から8問に増え、2021年12月のABC233から問Hの名前が問Exに変更された。90問全て解けば現代のABCの8問のうち5問はカバーされていそう。6,7問は調子よくて時間が間に合えば応用できる人ならいけそう。問Exは典型90問だけじゃカバーしきれないので、別の方法で対策したい。

〇〇100本ノックのつもりで典型90問に挑戦するとあまりの難易度に驚くかもしれない。

個別問題の感想

006 Smallest Subsequence

「辞書順最小は貪欲」を金言にしている。「長さが固定なら先頭から決める」「長さが不定なら末尾から決める」という解き方がよくある。
想定解と同様に、こういう文字列の問題はよく次のテーブルを使っている。

nxt[i][c] := S の i 文字目以降で文字 c が初めて現れるインデックス。

メモリ使用量が多いがクエリをテーブルにメモしているので実装するときに便利。

013 Passing

90問の中でダイクストラ法を使うのはこの問題だけなので必ず正解しておきたい。

035 Preserve Connectivity

この問題は当時Twitter上で話題になっていた記憶がある。別解の「Auxiliary Tree (補助木)」という名前が聞きなれないので。
極端な話、ダイクストラ法のヒープも補助木、クラスカル法のDSUも補助木、と言えなくもないので自分が専門用語として使いたいときは定義を書く必要があると思った。

040 Get More Money

必ず Project selection problem という名前も覚える。検索すれば Wikipedia (link) や、より詳しい解説が見つかるかもしれない。

043 Maze Challenge with Lack of Sleep

拡張ダイクストラについて、頂点数無限のグラフ上でキューにプッシュするまでその頂点を陽に作らないようなダイクストラ法の実装のことだと思っていた。それは誤りで正しくは、与えられたグラフの頂点数を増やしたグラフでのダイクストラ法のことを拡張ダイクストラと呼ぶようだ。

047 Monochromatic Diagonal

別解として書かれているが Z-algorithmでも解ける。この問題に対する解法はいつも「先頭からm文字v.s.途中からm文字」の比較になっているので。
Rolling hashなら「途中からv.s.途中から」の比較ができるので解ける問題も広くて良いのだが、実際はどちらでも難易度が変わらないなら Z-algorithm を優先して使うことが多い。Rolling hashは問題ごとに衝突の可能性を検討する必要があるから。

051 Typical Shop

読者の課題の O(2^(n/2)) のアルゴリズムを考えたい。これはマージソートでも使われる「マージマージ - Wikipedia」を知っていればできる。

マージ
入力：2つのソートされた数列 A, B
出力：AとBの要素を全て含む、1つのソートされた数列 C

C++なら std::merge として実装されているがこれは AとBの長さの和を n として Θ(n) 時間のアルゴリズムである。
これを利用すると半分の要素の組み合わせを全列挙するときにソートが必要なくなり、Θ(2^(n/2)) になる。その後、もう半分と適合する要素を探すときは二分法ではなく尺取り法などで範囲を探せば全体でもΘ(n * 2^(n/2)) ではなくΘ(2^(n/2)) のアルゴリズムを達成できる。

053 Discrete Dowsing

三分探索や黄金分割探索ができる関数とは「上に凸な関数」というのはよくない。Unimodal (単峰) 関数の方が正確でこれは「凸関数」を含む。単峰性をもつ滑らかな関数は「途中までは傾きが正、途中からは傾きが負」の関数である、正と負のあいだに傾きが0の区間があってもよいが傾きが0の区間は峰の一箇所のみ。実際に問053は凸ではない（数列を折れ線で結んだものを関数だとする場合）。

凸性：微分した関数が広義単調減少
単峰性：微分した関数は、正から0、0から負と変化する

055 Select 5

「読者への課題」の N^5 より計算量の良いアルゴリズムについて。Pが素数のときは4重ループで最後の1要素をHashSetで見つければよい。しかし、一般のPについてはいまだ思いついてない。

067 Base 8 to 9

やるべきことは文字列 -> 整数 -> 文字列という2段階の変換。
整数型のことを10進法とは呼ばない気がする。

2021-08-07

読書感想文「ガードナーの数学パズル・ゲーム」

本

「完全版マーティン・ガードナーの数学ゲーム全集」の1～4巻を読んだ。その1巻「ガードナーの数学パズル・ゲーム」の感想

シリーズについて

本書はMartin Gardnerさんが月刊雑誌「Scientific American」で書いていた「数学ゲーム」というコラムのまとめ。レクリエーション数学、つまり、数学パズル・ゲーム・工作・手品・クイズ・リドルなどの記事を再編集してまとめたもの。1巻は16章あるがそれぞれの関連性は薄く、どこから読んでも専門的な知識がなくても楽しめる内容になっている。各章の末尾には付録として追記・読者からの反応・問題の答え・参考文献も充実していて詳しい。また翻訳も良く、英語の言葉遊びの補足があったり、参考文献の書籍の翻訳があれば追記していたりして素晴らしい。
書きたいことがある章についてこのブログで面白かったよとだけ書く。

良い知らせ

本シリーズは全15巻という大ボリューム、おそらくすべての記事を再編している。過去に出版されたものをケンブリッジ大学が再編集して Mathematical Association of America (MAA、アメリカ数学協会) が出版し、日本語翻訳が日本評論社から出版される。
ちなみに巻号が多少前後している。

悪い知らせ

現在4巻まで出ているがそれ以降は出ていない。3巻の英語版が2009年、4巻が2014年、そして2021年になっても5巻は出ていない。仮に残り11冊が5年間隔で出たとしても翻訳版まで完結するのは50年後か。
生きているうちに読むことはできないだろう。

タイトル等はここから確認できる。Martin Gardner bibliography - Wikipedia
日本語のタイトルは本書のカバーに書いてある。

f:id:natsugiri:20210807051740p:plain:w500 — 日本語題名

13章ポリオミノ

特に正方形5つからなるペントミノを詳しく紹介している。ペントミノは正方形の12個のピースからなるパズルで、それぞれが5つの正方形を連結した異なる図形になっている。
ペントミノは玩具として売られているが自作してみた。アクリル製の1cm角の立方体が「ブランクダイス」という名前でボードゲームの小道具として売られていたのでこれを材料とする。

f:id:natsugiri:20210807052435p:plain:w400 — ブランクダイス

接着剤でつないだ。

f:id:natsugiri:20210807053005p:plain:w400 — ペントミノ

自作するメリットとして好きなサイズで作ることができ、1x1ミノや2x2ミノなどを追加した拡張問題も遊ぶことができる。正方形を繋いでもできるが立方体で作れば3次元的な積み木パズルも遊ぶことができる。さらに単色で作るとミノの切れ目がわからないので画像をアップしてもネタバレにならない。なので3x20の画像をここに貼っておく。

f:id:natsugiri:20210807053433p:plain:w600 — 3x20

しかし一度置いたミノを動かそうとするとどれがどのミノかわからないので悲しい。

ペントミノを使って作る長方形・立体の問題例として

6x10
5x12
4x15
3x20
3x4x5
5x6を2組

などがある。
本書によると上記の問題の中で3x20の解の数が最も少ないので最も難しい問題としている。
ガードナーさんは回転・反転を除いた解の数に興味があるようで、そのような数え上げがこの章に限らず度々出てくる。
他にも一直線で2つに分離できないので美しいとか、4つのミノが集まる点が無いので美しいとかステレオタイプな数学者っぽい。

その他

1巻は読み物よりもポリオミノのようなパズルや、ほかにも工作やボードゲームなどアクティブでビジュアルなものが多いので面白い。
例えば4章では3目並べを扱っている。内容としては3目並べのOXを取り除いたりスライドさせたりするバリエーション・大きなサイズや3次元への拡張についての紹介や考察が主である。
しかし特に面白いのは最もベーシックな3目並べの戦略を紹介しているところ。
3目並べは先手後手のどちらも負けを回避することができるゲームとして知られているが、どの着手ならば相手が間違いやすいか、初心者は気が付きにくいかなどを考えている。

2021-05-29

Parking Function の数は (n+1)^{n-1}

数学

Parking Function、駐車関数、木

Parking Function

$n$ 台の車( $1, \cdots, n$ ) が順番に駐車場に入ってくる。駐車スペースは $n$ 個 ( $1, \cdots, n$ ) ある。
1番目の車から順番に駐車する。 $i$ 番目の車は駐車スペース $a_i$ に停めようとする ( $1 \le a_i \le n$ )。このとき、空いていない場合は $a_i + 1$ 、それでも空いていない場合は $a_i + 2$ と次々に隣に停めようとする。
駐車スペース $n$ も空いていない場合は駐車することができず、（ほかの場所が空いていたとしても）失敗する。どこかに駐車した場合、次の車が入ってくる。

数列 $a_1, \cdots, a_n$ について、 $n$ 台すべての車が駐車できる場合、数列 $a$ を Parking Function と呼ぶ。

問題

長さ $n$ の Parking Function は何通りあるか求めよ。

例 $n=2$

3通り。
$a = (1, 1)$
$a = (1, 2)$
$a = (2, 1)$

答え

Parking Function の個数を $f(n)$ とすると、 $f(n) = (n+1)^{n-1}$ 。

上記の問題の代わりに駐車スペースが円形に並んだような問題を考える。
駐車スペース $n+1$ を追加して考える。このとき Parking Function とは限らない数列は $1 \le a_i \le n+1$ $(1 \le i \le n)$ を満たす $(n+1)^n$ 通りが考えられる。
車は駐車スペース $n+1$ にも停めようとする。さらに、駐車スペース $n+1$ が空いていない場合は駐車スペース $1$ に戻って停めようとし、空いていない場合は $2, 3, \cdots$ と同様に停めようとする場合を考える。

この場合であれば全ての車が駐車することができ、最後には駐車スペースが一箇所だけ空いている。
$(n+1)^n$ の数列に対して最後に空く駐車スペースは $1 \cdots n+1$ が均等に現れ、それぞれ $(n+1)^{n-1}$ 通り。そして「最後に $n+1$ が空いている」ことと「 $a$ は Parking Function」は同値である。

よって元の問題の答えは $f(n) = (n+1)^{n-1}$ 。

f:id:natsugiri:20210529101238p:plain — parking

ケイリーの公式 (Cayley's formula)

$n+1$ 頂点のラベル付き木構造の数は $(n+1)^{n-1}$ であり (ケイリーの公式)、Parking Function と一致する。なので１対１で対応させるようなアルゴリズムの１つを書く。

アルゴリズム

Philippe Chassaing と Jean-François Marckert によるアルゴリズム。
コードの簡単さのため計算量が悪いが、小さい工夫で O(n) になる。

入力：長さ $n$ の Parking Function を満たす数列 $a$
出力：頂点ラベルが $0, \cdots, n$ の木構造

Q : 頂点を持つQueue
push(Q, 0)
for k in (1, ..., n) {
  for i in (1, ..., n) {
    if a_i == k {
      add_edge(front(Q), i)
      push(Q, i)
    }
  }
  pop(Q)
}

逆向きの写像は頂点0からBFSする。

終わりに

次の2つの内、1つでも満たすような数列も Parking Function である。

任意の非負整数を加算することを任意の回数行うことで、 $1,\cdots,n$ の置換を得ることができる
ソートし得られた数列 $a'$ について、任意の $i$ $(1 \le i \le n)$ において $1 \le a'_i \le i$ が成り立つ

以下は全て $(n+1)^{n-1}$ 通りある。

長さ $n$ の Parking Function の数
$n+1$ 頂点のラベル付き木の数
$n+1$ 頂点の辺ラベル付き根付き木の数
$n$ 頂点のラベル付き根付き森の数

辺ラベル付き根付き木はアルゴリズムで0を根とすれば得られる。
根付き森はアルゴリズムで得られた木の頂点 0 を取り除くことで得られる。
そのほかの $(n+1)^{n-1}$ については A000272 - OEIS。

参考文献

Richard P. Stanley, A Survey of Parking Functions (slide:http://www-math.mit.edu/~rstan/transparencies/parking3.pdf)
Philippe Chassaing, Jean-François Marckert, Parking functions, empirical processes, and the width of rooted labeled trees

2021-05-02

全域最小カット (Stoer-Wagner algorithm)

グラフ

Global Minimum Cut
Stoer-Wagner algorithm
無向グラフに対して、あらゆるペア(s, t)のカットの中で最小の s-t-カットを求める。

問題

重み付無向グラフが与えられる。各頂点にSかTを割り当てたとき、一端がSでもう一端がTの辺の重みの総和をその「割り当ての重み」とする。割り当ての重みの最小値を求めよ。

SとTはそれぞれ少なくとも1つ以上の頂点に割り当てなければならない。
重み 0以上
多重辺、自己ループあり
非連結あり

Stoer-Wagner algorithm

MinCutPhaseを実行すると、ある(s, t)に対して最小s-t-カットを求めることが出きる（ここがすごい）。
これがGlobalMinCutかもしれない、そうでない場合のために、s, tをマージしたグラフでも再びMinCutPhaseを実行する。

MinCutPhase

適当な1頂点aから始める。S-T-カットのS側は頂点aのみ、T側は残りの全ての頂点。
「最も重み合計の大きい頂点」を順番にS側に移動していく。T側に1頂点残った時に、「S側に最後に追加した頂点s」と「T側に最後に残った頂点t」について最小 s-t-カットになっている。
s-tについては最小だがglobal min cutとは限らない。どのs, tが残るのかはよくわからない。

計算量

隣接行列を用いた実装だとO(n^3)
隣接リスト + ヒープ O(n m log m)
隣接リスト + increase-keyを実装したヒープ O(n m + n^2 log n)

参考までに、s=1と固定してtをそれ以外の頂点全て試してDinic法 O(n^2 m) を実行して最小カットを求める場合、O(n^3 m)。

参考

Stoer–Wagner algorithm - Wikipedia (C++実装)
Spaghetti Source - 無向グラフの全域最小カット (Nagamochi-Ibaraki/Stoer-Wagner) (C++実装)
全域最小カット (Stoer-Wagner Algorithm) - yaketake08's 実装メモ (Python実装、ヒープ実装)

オンラインジャッジ

UVa 10989 - Bomb, Divide and Conquer Online Judge
ICC 2021 & SRM 804 DIV 1 (problem-700 CostMaximizer) Topcoder SRM 804 & International Coding Challenge w/ $300 in Prizes - Codeforces

コード

O(n^3)

const int MAXN = 511;
using Weight = long long;

int n;
Weight adj[MAXN][MAXN];
Weight cost[MAXN];
bool used[MAXN];
bool added[MAXN];
int group[MAXN];

Weight best_weight; // global mimum cut;
// cut[v] == ('S' or 'T');
char cut[MAXN+1];

void init(int n_) {
    assert(2 <= n_ && n_ <= MAXN);
    n = n_;
    REP (i, n) memset(adj[i], 0, sizeof (Weight) * n);
}

// add undirected edge;
void add_edge(int x, int y, Weight weight) {
    assert(0 <= x && x < n);
    assert(0 <= y && y < n);
    assert(weight >= 0);

    adj[x][y] += weight;
    adj[y][x] += weight;
}

// find global minimum cut;
Weight solve() {
    memset(used, 0, sizeof (bool) * n);
    REP (i, n) group[i] = i;
    cut[n] = 0;
    best_weight = -1;

    for (int phase=n-1; phase>=0; phase--) {
	memcpy(cost, adj[0], sizeof (Weight) * n);
	memcpy(added, used, sizeof (bool) * n);
	int prev, last = 0;
	REP (i, phase) {
	    prev = last;
	    last = -1;
	    // last: the most tightly connected vertex;
	    for (int j=1; j<n; j++) {
		if (!added[j] && (last == -1 || cost[j] > cost[last])) last = j;
	    }
	    if (i == phase - 1) {
		if (best_weight == -1 || cost[last] < best_weight) {
		    // (prev, last)-cut;
		    best_weight = cost[last];
		    // update mimimum cut;
		    REP (j, n) cut[j] = (group[j] == last? 'T': 'S');
		}
		REP (j, n) adj[prev][j] += adj[last][j]; // merge;
		REP (j, n) adj[j][prev] = adj[prev][j]; // copy edge cost;
		used[last] = true;
		REP (j, n) if (group[j] == last) group[j] = prev;
	    } else {
		REP (j, n) cost[j] += adj[last][j];
		added[last] = true;
	    }
	}
    }

    return best_weight;
}

使い方

UVa 10989。

void MAIN() {
    int N, M;
    scanf("%d%d", &N, &M);
    init(N);
    REP (i, M) {
	int x, y, c;
	scanf("%d%d%d", &x, &y, &c);
	x--; y--;
	add_edge(x, y, c);
    }
    LL ans = solve();
    printf("%lld\n", ans);
}

またcutの頂点集合も求めている。cut[i] == 'S' ならばS側、cut[i] == 'T' ならT側。