HDU 1045 Fire Net(DFS or bipartite graph match)
Description
给出一个地图,有空地,有墙,在空地上安排炮台,炮台会向四方攻击,但不会穿透墙壁,要避免炮台彼此攻击到,求最多能安排多少炮台?
Analyze
可以简单のDFS
另外的二分图匹配:
假设没有墙壁,为每行、每列标号,针对每个点进行建边,求最大匹配
1 | 1 | 1 | 1 |
---|---|---|---|
2 | 2 | 2 | 2 |
3 | 3 | 3 | 3 |
4 | 4 | 4 | 4 |
1 | 2 | 3 | 4 |
---|---|---|---|
1 | 2 | 3 | 4 |
1 | 2 | 3 | 4 |
1 | 2 | 3 | 4 |
建边add(1, 1)add(1, 2)add(1, 3)add(1,4)add(2,1)……
在求最大匹配时,假设第一个表中的2匹配了第二个表中的3,那么相当于在第二行第三列建一座炮台,由于本行都是2,且2已经被分配,所以本行不会再被分配炮台;同理,本列都是3,且3已经被分配,所以本列不会再被分配炮台。如此限制了同行或同列不会出现两座炮台。
现在有墙,标号便可增加了,比如样例
- 1
- 2
- 3
- 4
- 5
1 | X | 2 | 2 |
---|---|---|---|
3 | 3 | 3 | 3 |
X | X | 4 | 4 |
5 | 5 | 5 | 5 |
1 | X | 5 | 6 |
---|---|---|---|
1 | 3 | 5 | 6 |
X | X | 5 | 6 |
2 | 4 | 5 | 6 |
Code
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
Code of DFS
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56