题目大意
我们已知$n$对夫妻的婚姻状况，称第$i$对夫妻的男方为$B_i$，女方为$G_i$。若某男$B_i$与某女$G_j$曾经交往过（无论是大学，高中，亦或是幼儿园阶段，$i\neq j$），则当某方与其配偶（即$B_i$与$G_i$或$B_j$与$G_j$）感情出现问题时，他们有私奔的可能性。不妨设$B_i$和其配偶$G_i$感情不和，于是$B_i$和$G_j$旧情复燃，进而$B_j$因被戴绿帽而感到不爽，联系上了他的初恋情人$G_k\ldots$一串串的离婚事件像多米诺骨牌一般接踵而至。若在$B_i$和$G_i$离婚的前提下，这$2n$个人最终依然能够结合成$n$对情侣，那么我们称婚姻$i$为不安全的，否则婚姻$i$就是安全的。
给定所需信息，你的任务是判断每对婚姻是否安全。
题目分析
这道题要求我们写前两道稳定婚姻问题的spj。
直接上二分图匹配。
当然用Tarjan缩点也可以。
代码
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
| #include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
#include<map>
using namespace std;
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
const int maxn=4005;
int n,m,My[maxn],Man;
bool vst[maxn];
vector<int>edges[maxn];
void AddEdge(int x,int y) {
edges[x].push_back(y);
}
bool Dfs(int Now) {
for(int Next:edges[Now]) {
if(vst[Next]||(Next==Man&&Now==Man))continue;
vst[Next]=1;
if(My[Next]==0||Dfs(My[Next])) {
My[Next]=Now;
return true;
}
}
return false;
}
string s1,s2;
map<string,int>M;
int main() {
ios::sync_with_stdio(false);
cin>>n;
for(int i=1; i<=n; i++) {
cin>>s1>>s2;
M[s1]=M[s2]=i;
AddEdge(i,i);
My[i]=i;
}
cin>>m;
for(int i=1; i<=m; i++) {
cin>>s1>>s2;
AddEdge(M[s1],M[s2]);
}
for(int i=1; i<=n; i++) {
memset(vst,0,sizeof(vst));
My[i]=0;
Man=i;
if(Dfs(i))puts("Unsafe");
else puts("Safe");
for(int j=1; j<=n; j++)My[j]=j;
}
return 0;
}
|
