給定一個 $n$ 個點 $m$ 條邊的無向無環圖
你可以在節點上放燈，每個燈可以照亮以它為端點的所有邊
目標是把所有邊都照亮，且在燈的總數最小的前提下，被兩盞燈同時照亮的邊應該盡量多
多個測資點，每個測資點多筆測資
每個測資點第一行有一正整數 $T$ 代表測資筆數 ( $T\leq 30$ )
每筆測資第一行有兩正整數 $n,m$ 代表圖的節點數和邊數 ( $m<n\leq 5\times 10^3$ )
接下來有 $m$ 行，每行兩個非負整數 $a,b$ 代表節點 $a,b$ 之間有一條邊
對於每筆測資，輸出三個整數 $sum, light_2, light_1$
即 燈的總數, 被兩個燈照亮的邊數, 只被一個燈照亮的邊數
2 4 3 0 1 1 2 2 3 5 4 0 1 0 2 0 3 0 4
2 1 2 1 0 4
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」 |
|||||