Marriage Match II(二分答案+最大流)

描述

传送门:HDU3081

Presumably, you all have known the question of stable marriage match. A girl will choose a boy; it is similar as the game of playing house we used to play when we are kids. What a happy time as so many friends playing together. And it is normal that a fight or a quarrel breaks out, but we will still play together after that, because we are kids.
Now, there are $2n$ kids, $n$ boys numbered from $1$ to $n$, and $n$ girls numbered from $1$ to $n$. you know, ladies first. So, every girl can choose a boy first, with whom she has not quarreled, to make up a family. Besides, the girl $X$ can also choose boy $Z$ to be her boyfriend when her friend, girl $Y$ has not quarreled with him. Furthermore, the friendship is mutual, which means $a$ and $c$ are friends provided that $a$ and $b$ are friends and $b$ and $c$ are friend.
Once every girl finds their boyfriends they will start a new round of this game—marriage match. At the end of each round, every girl will start to find a new boyfriend, who she has not chosen before. So the game goes on and on.
Now, here is the question for you, how many rounds can these $2n$ kids totally play this game?

Input

There are several test cases. First is a integer $T$, means the number of test cases.
Each test case starts with three integer $n, m$ and $f$ in a line $(3≤n≤100,0<m<n*n,0≤f<n)$. $n$ means there are $2 \times n$ children, $n$ girls(number from $1$ to $n$) and $n$ boys(number from $1$ to $n$).
Then $m$ lines follow. Each line contains two numbers $a$ and $b$, means girl $a$ and boy $b$ had never quarreled with each other.
Then $f$ lines follow. Each line contains two numbers $c$ and $d$, means girl $c$ and girl $d$ are good friends.

Output

For each case, output a number in one line. The maximal number of Marriage Match the children can play.

Sample Input

1
2
3
4
5
6
7
8
9
1
4 5 2
1 1
2 3
3 2
4 2
4 4
1 4
2 3

Sample Output

1
2

思路

  • 由于女孩之间的朋友具有传递关系,所以我们先用floyd对女孩之间的朋友关系图传递闭包,从而得出每个女孩的备选男孩。
  • 我们要求游戏最多可以进行几轮,可以考虑二分答案,假设答案为$mid$。建图方式如下:
    • 女孩编号:$0 \sim n-1$;
    • 男孩编号:$n \sim 2n-1$;
    • 超级源点:$2n$;
    • 超级汇点:$2n+1$;
    • 超级源点→女孩:容量为$mid$;
    • 男孩→超级汇点:容量为$mid$;
    • 女孩→其可选的男孩:容量为$1$。
  • 若上图跑出的最大流为$mid \times n$,则说明当前答案可行,L=mid+1,否则R=mid-1
  • 本题还可以用二分图匹配来做,即首先建立女孩与男孩的二分图,并且连好可能的边. 然后进行一轮匹配,如果此时有完美匹配,那么就删除这些匹配边,进行第二轮匹配,如果还有完美匹配,就继续……

代码

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
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
#include <bits/stdc++.h>
using namespace std;
#define clr(a,x) memset(a, x, sizeof(a))
#define mp(x,y) make_pair(x,y)
#define pb(x) push_back(x)
#define X first
#define Y second
#define fastin ios_base::sync_with_stdio(0);cin.tie(0);
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef vector<int> VI;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-6;

const int maxn = 205;
const int maxm = 105;
bool C[maxm][maxm], F[maxm][maxm];
struct Edge
{
int from, to, cap, flow;
Edge(int u, int v, int c, int f): from(u), to(v), cap(c), flow(f) {}
};
struct Dinic
{
int n, m, s, t; //结点数,边数(包括反向弧),源点编号和汇点编号
vector<Edge> edges; //边表。edge[e]和edge[e^1]互为反向弧
vector<int> G[maxn]; //邻接表,G[i][j]表示节点i的第j条边在e数组中的序号
bool vis[maxn]; //BFS使用
int d[maxn]; //从起点到i的距离
int cur[maxn]; //当前弧下标
void init(int n)
{
this->n = n;
for (int i = 0; i < n; i++) G[i].clear();
edges.clear();
}
void AddEdge(int from, int to, int cap)
{
edges.pb(Edge(from, to, cap, 0));
edges.pb(Edge(to, from, 0, 0));
m = edges.size();
G[from].pb(m - 2);
G[to].pb(m - 1);
}
bool BFS()
{
clr(vis, 0);
clr(d, 0);
queue<int> q;
q.push(s);
d[s] = 0;
vis[s] = 1;
while (!q.empty())
{
int x = q.front();
q.pop();
for (int i = 0; i < G[x].size(); i++)
{
Edge& e = edges[G[x][i]];
if (!vis[e.to] && e.cap > e.flow)
{
vis[e.to] = 1;
d[e.to] = d[x] + 1;
q.push(e.to);
}
}
}
return vis[t];
}
int DFS(int x, int a)
{
if (x == t || a == 0) return a;
int flow = 0, f;
for (int& i = cur[x]; i < G[x].size(); i++)
{
//从上次考虑的弧
Edge& e = edges[G[x][i]];
if (d[x] + 1 == d[e.to] && (f = DFS(e.to, min(a, e.cap - e.flow))) > 0)
{
e.flow += f;
edges[G[x][i] ^ 1].flow -= f;
flow += f;
a -= f;
if (a == 0) break;
}
}
return flow;
}
int Maxflow(int s, int t)
{
this->s = s;
this->t = t;
int flow = 0;
while (BFS())
{
clr(cur, 0);
flow += DFS(s, INF);
}
return flow;
}
} ans;

void floyd(int n)
{
for (int i = 0; i < n; i++)
F[i][i] = true;
for (int k = 0; k < n; k++)
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
F[i][j] |= F[i][k] & F[k][j];
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (F[i][j])
for (int k = 0; k < n; k++)
C[i][k] |= C[j][k];
}

bool ok(int mid, int n)
{
int s = n << 1;
int t = n << 1 | 1;
ans.init(t + 1);
for (int i = 0; i < n; i++)
{
ans.AddEdge(s, i, mid);
ans.AddEdge(n + i, t, mid);
}
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (C[i][j])
ans.AddEdge(i, n + j, 1);
return ans.Maxflow(s, t) == mid * n;
}

int main()
{
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
#endif
fastin
int t, n, m, f, u, v;
cin >> t;
while (t--)
{
clr(C, 0);
clr(F, 0);
cin >> n >> m >> f;
while (m--)
{
cin >> u >> v;
C[u - 1][v - 1] = true;
}
while (f--)
{
cin >> u >> v;
F[u - 1][v - 1] = true;
F[v - 1][u - 1] = true;
}
floyd(n);
int L = 0, R = n, res;
while (L <= R)
{
int mid = (L + R) >> 1;
if (ok(mid, n))
res = mid, L = mid + 1;
else
R = mid - 1;
}
cout << res << endl;
}
return 0;
}
捐助作者
0%