Minimizing Edges
다이아몬드 II의견: 0
Bessie has a connected, undirected graph \(G\) with \(N\) vertices labeled
\(1\ldots N\) and \(M\) edges (\(2\le N\le 10^5, N-1\le M\le \frac{N^2+N}{2}\)). \(G\)
may contain self-loops (edges from nodes back to themselves), but no parallel
edges (multiple edges connecting the same endpoints).
Let \(f_G(a,b)\) be a boolean function that evaluates to true if there exists a
path from vertex \(1\) to vertex \(a\) that traverses exactly \(b\) edges for each
\(1\le a\le N\) and \(0\le b\), and false otherwise. If an edge is traversed
multiple times, it is included that many times in the count.
Elsie wants to copy Bessie. In particular, she wants to construct an undirected
graph \(G'\) such that \(f_{G'}(a,b)=f_G(a,b)\) for all \(a\) and \(b\).
Elsie wants to do the least possible amount of work, so she wants to construct
the smallest possible graph. Therefore, your job is to compute the minimum
possible number of edges in \(G'\).
Each input contains \(T\) (\(1\le T\le 5\cdot 10^4\)) test cases that should be
solved independently. It is guaranteed that the sum of \(N\) over all test cases
does not exceed \(10^5\), and the sum of \(M\) over all test cases does not exceed
\(2\cdot 10^5\).
Problem credits: Benjamin Qi
SCORING
- All test cases in input 3 satisfy \(N\le 5\).
- All test cases in inputs 4-5 satisfy \(M=N\).
- For all test cases in inputs 6-9, if it is not the case that \(f_G(x,b)=f_G(y,b)\) for all \(b\), then there exists \(b\) such that \(f_G(x,b)\) is true and \(f_G(y,b)\) is false.
- All test cases in inputs 10-15 satisfy \(N\le 10^2\).
- Test cases in inputs 16-20 satisfy no additional constraints.
Problem credits: Benjamin Qi
The first line of the input contains \(T\), the number of test cases.
The first line of each test case contains two integers \(N\) and \(M\).
The next \(M\) lines of each test case each contain two integers \(x\) and \(y\)
(\(1\le x\le y\le N\)), denoting that there exists an edge between \(x\) and \(y\) in
\(G\).
Consecutive test cases are separated by newlines for readability.
For each test case, the minimum possible number of edges in \(G'\) on a new line.
2
5 5
1 2
2 3
2 5
1 4
4 5
5 5
1 2
2 3
3 4
4 5
1 54
5In the first test case, Elsie can construct \(G'\) by starting with \(G\) and
removing \((2,5)\). Or she could construct a graph with the following edges,
since she isn't restricted to just removing edges from \(G\):
1 2
1 4
4 3
4 5
Elsie definitely cannot do better than \(N-1\) since \(G'\) must also be connected.
7
8 10
1 2
1 3
1 4
1 5
2 6
3 7
4 8
5 8
6 7
8 8
10 11
1 2
1 5
1 6
2 3
3 4
4 5
4 10
6 7
7 8
8 9
9 9
13 15
1 2
1 5
1 6
2 3
3 4
4 5
6 7
7 8
7 11
8 9
9 10
10 11
11 12
11 13
12 13
16 18
1 2
1 7
1 8
2 3
3 4
4 5
5 6
6 7
8 9
9 10
9 15
9 16
10 11
11 12
12 13
13 14
14 15
14 16
21 22
1 2
1 9
1 12
2 3
3 4
4 5
5 6
6 7
7 8
7 11
8 9
8 10
12 13
13 14
13 21
14 15
15 16
16 17
17 18
18 19
19 20
20 21
20 26
1 2
1 5
1 6
2 3
3 4
4 5
4 7
6 8
8 9
8 11
8 12
8 13
8 14
8 15
8 16
8 17
9 10
10 18
11 18
12 19
13 20
14 20
15 20
16 20
17 20
19 20
24 31
1 2
1 7
1 8
2 3
3 4
4 5
5 6
6 7
6 9
8 10
10 11
10 16
10 17
10 18
10 19
10 20
11 12
12 13
13 14
14 15
15 16
15 17
15 18
15 19
15 20
15 21
15 22
15 23
15 24
21 22
23 2410
11
15
18
22
26
31In each of these test cases, Elsie cannot do better than Bessie.
riseoj 작성
출처 올림피아드 > USACO > 2020-2021 > February > Platinum
평가 및 의견
Minimizing Edges
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Minimizing Edges