'공부/ACM' 카테고리의 글 목록

'공부/ACM'에 해당되는 글 3건

2008.06.04 [알고리즘] Maximum Flow
2008.05.21 UVA 10147 - [Test Case] Highways
2008.05.14 UVA 11331 - [Test Case] The Joys of Farming

공부/ACM2008. 6. 4. 18:37

[알고리즘] Maximum Flow

http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=maxFlow
적절한 설명이 괜찮다.

Pseudo Code도 깔끔하고 좋다. (난 사실 그간 Maximum Flow는 DFS로만 썼는데, 그게 얼마나 비효율적인지를 깨달았... Priority Queue는 귀찮아서 써보진 않았다;)

관련문제: ACM UVA 10080

Posted by Jyui

공부/ACM2008. 5. 21. 09:42

UVA 10147 - [Test Case] Highways

Input:
3
9
1 5
0 0
3 2
4 5
5 1
0 4
5 2
1 2
5 3
3
1 3
9 7
1 2
4
0 0
0 1
1 1
1 0
4
1 2
1 3
2 4
3 4
5
0 0
0 1
1 1
1 0
2 0
5
1 2
2 3
3 4
4 1
2 4

Output:
(각 케이스별 Output의 순서는 관계없음. 즉 아래의 첫번째 테스트 케이스의 경우,
1 6
3 7
4 9
5 7
8 3
이런식이어도 무방함. 각 테스트 케이스 사이에는 한줄의 blank line이 들어감)
5 7
1 6
3 8
3 7
4 9

No new highways need

4 5

Posted by Jyui

공부/ACM2008. 5. 14. 02:03

UVA 11331 - [Test Case] The Joys of Farming

Input:
5
4 8 8
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9

3 2 4
1 2
2 3
3 1
2 4

4 8 6
1 2
3 4
5 6
7 8
9 10
11 12

10 3 9
1 2
2 3
4 6
9 8
1 9
10 11
13 6
5 8
12 7

7 7 8
1 2
3 4
5 6
1 7
1 8
1 9
8 9
2 9

Output:
yes
no
no
no
no