是么时二分图
这个图的节点可以被分为两个集合, 使得同一集合内没有连边。
匈牙利算法
例题
IOI 有 $m$ 道题, HPY 会 $n$ 个算法, 一共有 $k$ 个算法可以解决IOI题。
HPY 会的算法太多了, 所有这次 IOI 用了这个算法, 等到下一次 IOI 时才会记其这个算法。
<h1 id="constraints">输入</h1>
第一行输入三个整数$ n $、$ m $和$ k $:HPY会的算法的数量、IOI题目的数量和可以解决题目的数量。HPY会的算法编号为$ 1,2,\dots,n $,IOI题目编号为$ 1,2,\dots,m $。
之后有$ k $行描述用算法可以解决的问题。每行有两个整数$ a $和$ b $:算法$ a $可以解决 IOI 的 $ b $ 号问题。
<h1 id="constraints">输出</h1>
首先打印一个整数$ r $:最大解决IOI题目数量。之后,打印$ r $行描述解决的题目。你可以打印任何有效的解决方案。
<h1 id="constraints">约束</h1>
<ul>
<li><span class="math inline">$ 1 \le n,m \le 500 $</span></li>
<li><span class="math inline">$ 1 \le k \le 1000 $</span></li>
<li><span class="math inline">$ 1 \le a \le n $</span></li>
<li><span class="math inline">$ 1 \le b \le m $</span></li>
</ul>
<h1 id="example">示例</h1>
<table class="vjudge_sample">
<thead>
<tr>
<th>Input</th>
<th>Output</th>
</tr>
</thead>
<tbody>
<tr>
<td><pre>3 2 4
1 1
1 2
2 1
3 1
</pre></td>
<td><pre>2
1 2
3 1
</pre></td>
</tr>
</tbody>
</table>
</div>
对于一个点, 如果它没有匹配, 找它能匹配的点, 如果可以没有匹配或者可以换一个匹配就可以
#include<bits/stdc++.h>
using namespace std;
const int N = 505;
vector<int>g[N];
int vis[N], n, m, q, u, v, ans, p[N];
bool dfs(int x){
if(vis[x]){
return 0;
}
vis[x] = 1;
for(auto v : g[x]){
if((!p[v] || dfs(p[v]))){
p[v] = x;
return 1;
}
}
return 0;
}
int main(){
cin >> n >> m >> q;
while(q--){
cin >> u >> v;
g[u].push_back(v);
}
for(int i = 1; i <= n; ++i){
for(int j = 1; j <= n; ++j){
vis[j] = 0;
}
ans += dfs(i);
}
cout << ans << '\n';
for(int i = 1; i <= m; ++i){
if(p[i]){
cout << p[i] << ' ' << i << '\n';
}
}
return 0;
}
时间复杂度 \(O(n \cdot (n + m))\)
空间复杂度 \(O(n + m)\)
时间复杂度更优秀的算法
首先跑一遍 BFS
, 求出这个序列的长度
跑一遍 DFS
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
vector<int>g[N];
int vis[N], p[N], dist[N], u, n, m, qq, ans, v, cnt[N];
queue<int>q;
bool dfs(int x){
if(vis[x]){
return 0;
}
vis[x] = 1;
for(auto v : g[x]){
if(p[v] == -1 || (dist[p[v]] == dist[x] + 1 && dfs(p[v]))){
cnt[x] = 1;
p[v] = x;
return 1;
}
}
return 0;
}
bool bfs(){
for(; q.size(); q.pop()){
}
for(int i = 0; i < n; ++i){
dist[i] = (!cnt[i]);
if(!cnt[i]){
q.push(i);
}
}
while(q.size()){
u = q.front();
q.pop();
for(auto v : g[u]){
if(p[v] == -1){
return 1;
}
if(!dist[p[v]]){
dist[p[v]] = dist[u] + 1;
q.push(p[v]);
}
}
}
return 0;
}
int main(){
cin >> n >> m >> qq;
for(int i = 0; i < m; ++i){
p[i] = -1;
}
while(qq--){
cin >> u >> v;
g[u].push_back(v);
}
while(bfs()){
for(int i = 0; i < n; ++i){
vis[i] = 0;
}
for(int i = 0; i < n; ++i){
ans += (!cnt[i] && dfs(i));
}
}
cout << ans << '\n';
for(int i = 0; i < m; ++i){
if(~p[i]){
cout << p[i] << ' ' << i << '\n';
}
}
return 0;
}
时间复杂度 \(O(n\sqrt{n})\)
空间复杂度 \(O(n)\)
标签:二分,le,匹配,int,算法,IOI,return,dist From: https://www.cnblogs.com/liuyichen0401/p/18284204