题解 P1407 【[国家集训队]稳定婚姻】
Baihua
2019-01-22 16:45:07
#### 这里介绍一种二分图匹配做法。
* 考虑题目所描述的过程，我们应该 **先拆散一对夫妻**，然后试图为被拆散的男方匹配。
* 题目所给出的夫妻在没有被拆散的的情况下，一定是一对一的，因此如果匹配成功，那么在 ** 匈牙利算法的最后阶段，那个没有被匹配的点一定是先前被拆散的 **
* 因此我们模拟这个过程 ：
1.拆散一对夫妇
2.试图重新匹配
3.如果匹配成功，那么他们就是不安全的
* 注意事项：
数组开到足够用的
* 下面是代码：
```
#include <iostream>
#include <fstream>
#include <algorithm>
#include <math.h>
#include <stdio.h>
#include <cstring>
#include <map>
#define re register
#define GC getchar()
#define Clean(X,K) memset(X,K,sizeof(X))
using namespace std ;
int Qread () {
int X = 0 ,F = 1;
char C = GC ;
while (C > '9' || C < '0') {
if (C == '-') F = -1 ;
C = GC ;
}
while (C >='0' && C <= '9') {
X = X * 10 + C - '0' ;
C = GC ;
}
return X *F ;
}
/*
头文件和准备工作
*/
const int Maxn = 8005 , Maxm = 20005 ;
int Men[Maxn] , Cnt = 0 , Low[Maxn] , Dfn[Maxn] , Vis[Maxn] , En = 0 , Head[Maxn] , N , M , Match[Maxn] , S[Maxn] , T = 0;
struct Edge {
int Fr , Gt , Nxt ;
};
Edge E[Maxm * 2] ;
void Adg (int X , int Y) {
++ En ;
E[En].Fr = X ;
E[En].Gt = Y ;
E[En].Nxt = Head[X] ;
Head[X] = En ;
}
map <string , int > A ;
bool DFS (int X) {
for (re int i = Head[X] ; i; i = E[i].Nxt ) {
if (Vis[E[i].Gt]) continue ;
Vis[E[i].Gt] = 1 ;
if (Match[E[i].Gt] == 0 || DFS (Match[E[i].Gt])) {
return true ;
}
}
return false ;
}
int main () {
//freopen ("P1407.in" , "r" , stdin) ;
Clean (Head , 0) , Clean (Match , 0), Clean (Low , 0) , Clean (Dfn , 0) , Clean(Vis , 0) ;
N = Qread () ;
for (re int i = 1 ; i <= N; ++ i) {
string S1 , S2 ;
cin >> S1 >> S2 ;
int X , Y ;
if (A[S1]) X = A[S1] ;
else A[S1] = X = ++ Cnt ;
if (A[S2]) Y = A[S2] ;
else A[S2] = Y = ++ Cnt ;
Match[Y] = X , Match[X] = Y ;
Men[X] =1 , Men[Y] = 0 ;
}
M = Qread () ;
for (re int i = 1 ; i <= M ; ++ i) {
string S1 , S2 ;
cin >> S1 >> S2 ;
int X = A[S1] , Y = A[S2] ;
Adg (X , Y) ;
}
/*
建立图
*/
for (re int i = 1 ; i <= Cnt ; ++ i) if (Men[i]) {
Clean (Vis , 0) ;
Match[Match[i]] = 0 ;
//拆散一对夫妇
if (DFS (i)) printf ("Unsafe\n") ;
else printf ("Safe\n") ;
Match[Match[i]] = i ;
//让他们重新连接，方便以后的操作。
}
fclose (stdin) ;
fclose (stdout);
return 0;
}
```
#### Thanks!