luogu P2055 [ZJOI2009]假期的宿舍

二分图匹配?

可能是我第一道二分图匹配的题吧,反正是前几道,太菜了。。。
我是看的题解,二分图匹配,匈牙利算法。

  1. 对于本校学生并且不回家,先直接让他们睡自己的床。
  2. 对于外校学生,枚举每一张床,如果他认识这床的主人,那么,第一种情况,没人要预定这张床,他直接睡下即可;第二种情况,这张床已经有人占了,那么就看看预定这张床的人能不能换一张,如果能,就让原来的人走,他留下。
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
#include<bits/stdc++.h>
using namespace std;

struct Solution{
int T, n;
vector<int> in, ho, match, book;
vector<vector<int> > e;

bool dfs(int x){
for(int i = 1; i <= n; i++){
if(!book[i] && in[i] && e[x][i] == 1){
book[i] = 1;
if(match[i] == 0 || dfs(match[i])){
match[i] = x;
return 1;
}
}
}
return 0;
}

bool work(){
for(int i = 1; i <= n; i++){
book = vector<int> (n + 1, 0);
if((in[i] == 0 || ho[i] == 0) && dfs(i) == 0){
return 0;
}
}
return 1;
}

void Solve(){
scanf("%d", &T);
while(T--){
scanf("%d", &n);
in = vector<int> (n + 1, 0);
ho = vector<int> (n + 1, 0);
match = vector<int> (n + 1, 0);
e.resize(n + 1);
for(int i = 1; i <= n; i++) e[i].resize(n + 1, 0);
for(int i = 1; i <= n; i++) scanf("%d", &in[i]);
for(int i = 1; i <= n; i++) scanf("%d", &ho[i]);
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
scanf("%d", &e[i][j]);
}
if(in[i] == 1) e[i][i] = 1;
}
if(work()) printf("^_^\n");
else printf("T_T\n");
}
}
};

int main(){
Solution().Solve();
return 0;
}

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×