UVa12668 - Attacking rooks(Maximum Bipartite Matching 二分匹配)

題目大意

給你一個西洋棋盤,會在這個棋盤上放一些小兵,你必須在這個棋盤中放入一些城堡,且保證城堡攻擊範圍不會有另外一個城堡
試問最多可以放幾個

題目連結

重點觀念

分析

  • 題目要求為,不讓城堡看到城堡,也就是城堡在的位置\((x,y)\),其 x 軸與 y 軸都不可以有其他城堡,除非有小兵擋住,那就是一個很明顯的二分圖,x 對 y 二分
  • 如果有小兵站在棋盤上,那我們應該要以小兵為分界線,分出兩個 x,y 軸,因為站在小兵兩旁的城堡是合法的
  • 再來我們相同的 x,y 軸都設定為同一號碼,不斷進行匹配即可。

參考連結

UVALive 6525 Attacking rooks 二分匹配 经典题 by 九野的博客
UVALive 6525 Attacking rooks(二分图最大匹配) by FDU_Nan

心得

這題我學了好久…,第一次寫到用棋盤來表達二分圖,一開始真的是完全不知道原來這裡要用二分圖阿XDDD,也學到原來可以將二分圖的節點內在放入很多的點,就可以做到讓題目的要求,太神了、太酷了,第一次學到。

希望學起來可以對我的未來有幫助

題目程式碼

有一些程式碼註解在 Maximum Bipartite Matching by 大衛的筆記 請供參考。

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
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136

#include <iostream>
#include <bits/stdc++.h>
#define LOCAL
#define int long long
#define MAXN 120
using namespace std;
vector<int> edge[MAXN*MAXN];
int graph[MAXN][MAXN];
int mx[MAXN*MAXN], my[MAXN*MAXN], vy[MAXN*MAXN]; //matchX, matchY, visitY
int ex[MAXN][MAXN], ey[MAXN][MAXN]; //edgeX, edgeY
int n, cnt;
string s;

bool dfs(int x){
for(auto y: edge[x]){
if(vy[y] == 1) continue;
vy[y] = 1;
if(my[y] == -1 || dfs(my[y])){
mx[x] = y;
my[y] = x;
return true;
}
}
return false;
}

int bipartite_matching(){
memset(mx, -1, sizeof(mx));
memset(my, -1, sizeof(my));
int ans = 0;

for(int i = 1; i <= cnt; i++){
memset(vy, 0, sizeof(vy));
if(dfs(i)) ans++;

}
return ans;
}

void connect_edge(){ //將棋盤轉換成二分圖的邊
for(int i = 1; i <= cnt; i++) edge[i].clear();

int x;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
if(graph[i][j] == 0){
x = ex[i][j];
edge[x].push_back(ey[i][j]); //這個點的相同 x,y 軸,組成一個邊
}
}
}

return;
}

void print_graph(){ //debug 與方便學習用
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
printf("%2d ", graph[i][j]);
}
printf("\n");
}
}

void print_ex(){ //debug 與方便學習用
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
printf("%2d ", ex[i][j]);
}
printf("\n");
}
}

void print_ey(){ //debug 與方便學習用
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
printf("%2d ", ey[i][j]);
}
printf("\n");
}
}

int32_t main()
{
#ifdef LOCAL
freopen("in1.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif // LOCAL
while(cin >> n){
memset(graph, 0, sizeof(graph)); //清空資料
memset(ex, 0, sizeof(ex));
memset(ey, 0, sizeof(ey));

//如果那一個 row or column 有小兵存在,那分裂後的 x 軸就從 n+1 開始依序 hash
cnt = n+1;
for(int i = 1; i <= n; i++){
cin >> s;
s = ' ' + s; //從 index 1 開始
for(int j = 1; j <= n; j++){
if(s[j] == 'X') graph[i][j] = cnt++; //表示這邊可以分裂 row and column
else graph[i][j] = 0;
}
}
//print_graph();

//y 軸,從前往後,判斷他們是否屬於同一個 y 軸
for(int i = 1; i <= n; i++) ey[0][i] = i;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
//如果有分裂,那就將 ey 點開始往前都變為新節點
if(graph[i][j]) ey[i][j] = graph[i][j];
else ey[i][j] = ey[i-1][j];
}
}
//print_ey(); cout << "\n";

//x 軸,從後往前,判斷他們是否屬於同一個 x 軸
for(int i = 1; i <= n; i++) ex[i][n+1] = i;
for(int i = n; i > 0; i--){
for(int j = 1; j <= n; j++){
//如果有分裂,那就將 ex 點開始往前都變為新節點
if(graph[j][i]) ex[j][i] = graph[j][i];
else ex[j][i] = ex[j][i+1];
}
}
//print_ex();

connect_edge();
int ans = bipartite_matching();
cout << ans << "\n";

}

return 0;
}
  • 版權聲明: 本部落格所有文章除有特別聲明外,均採用 Apache License 2.0 許可協議。轉載請註明出處!
  • © 2020-2024 John Doe
  • Powered by Hexo Theme Ayer
  • PV: UV: