Login with GitHub. Nope?
修正 C++ 的程式碼在使用一定量動態記憶體後會產生 RF 的問題 @ 2019/12/6 4:45pm NeoHOJ 強勢復活中 (Open beta)
Submit  Ranklist

Problem : 365 - 2B. 來加邊吧!

Problem Statistics

Solved Member: 13  Submission: 58  User Tried: 13

Statement:

有 N 點 M 邊的有向圖,點從 1 編號 N。我們用 (i,j) 來表示由 i 連到 j 的有向邊。

你每次可以做一種操作:
step 1:挑 1 個點 x,並選擇 x 連出的兩個點 y,z
step 2:加上邊 (y,z) 跟 (z,y) (如果邊原本就存在的話則不加)

你可以依照任意順序加上你想要的邊,直到不能加任何邊為止。
問你最多可以讓整張圖有幾條有向邊?

Input:Output:

第一行有兩個整數 N,M,代表點數和有向邊的數量。
接下來 M 行,每行兩個整數 Ai,Bi,代表有一條從 Ai 連到 Bi 的有向邊。

限制:
1 ≤ N ≤ 100000
1 ≤ M ≤ 200000
1 ≤ Ai,Bi ≤ N
輸入沒重邊,沒自環

Subtask 1:(5分)
N ≤ 100

Subtask 2:(30分)
N ≤ 5000
輸出一個數字,代表加邊之後,最多能有幾條有向邊。

Sample Input:Sample Output:

5 4
1 2
1 3
4 3
4 5
10

HINT:

範例測資解釋:
1. x=1, y=2, z=3,加上 (2,3) (3,2) 兩條邊
2. x=4, y=3, z=5,加上 (3,5) (5,3) 兩條邊
3. x=3, y=2, z=5,加上 (2,5) (5,2) 兩條邊

變成 4+6=10 條邊

Source:

2013/2014 JOI 合宿 2模(日本IOI國手考)

Problem Setter

Testdata:

TestTimeMemoryScore
0500ms262144kb
1-1500ms262144kb5
1-2500ms262144kb
1-3500ms262144kb
1-4500ms262144kb
1-5500ms262144kb
1-6500ms262144kb
1-7500ms262144kb
1-8500ms262144kb
1-9500ms262144kb
1-10500ms262144kb
1-11500ms262144kb
1-12500ms262144kb
1-13500ms262144kb
1-14500ms262144kb
1-15500ms262144kb
1-16500ms262144kb
1-17500ms262144kb
1-18500ms262144kb
2-1500ms262144kb30
2-2500ms262144kb
2-3500ms262144kb
2-4500ms262144kb
2-5500ms262144kb
2-6500ms262144kb
2-7500ms262144kb
2-8500ms262144kb
2-9500ms262144kb
2-10500ms262144kb
2-11500ms262144kb
2-12500ms262144kb
2-13500ms262144kb
2-14500ms262144kb
2-15500ms262144kb
2-16500ms262144kb
2-17500ms262144kb
2-18500ms262144kb
2-19500ms262144kb
2-20500ms262144kb
2-21500ms262144kb
2-22500ms262144kb
2-23500ms262144kb
2-24500ms262144kb
2-25500ms262144kb
2-26500ms262144kb
2-27500ms262144kb
2-28500ms262144kb
3-1500ms262144kb65
3-2500ms262144kb
3-3500ms262144kb
3-4500ms262144kb
3-5500ms262144kb
3-6500ms262144kb
3-7500ms262144kb
3-8500ms262144kb
3-9500ms262144kb
3-10500ms262144kb
3-11500ms262144kb
3-12500ms262144kb
3-13500ms262144kb
3-14500ms262144kb
3-15500ms262144kb
3-16500ms262144kb
3-17500ms262144kb
3-18500ms262144kb
3-19500ms262144kb
3-20500ms262144kb
3-21500ms262144kb
3-22500ms262144kb
3-23500ms262144kb
3-24500ms262144kb
3-25500ms262144kb
3-26500ms262144kb
3-27500ms262144kb
3-28500ms262144kb
3-29500ms262144kb
3-30500ms262144kb
3-31500ms262144kb
3-32500ms262144kb
3-33500ms262144kb
3-34500ms262144kb
3-35500ms262144kb
3-36500ms262144kb
3-37500ms262144kb