首页 > 其他分享 >二分图匹配

二分图匹配

时间:2024-07-04 17:35:52浏览次数:15  
标签:二分 le 匹配 int 算法 IOI return dist

是么时二分图

这个图的节点可以被分为两个集合, 使得同一集合内没有连边。

匈牙利算法

例题
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

相关文章

  • 二分图匹配——从入门到入土
    基础知识形式化定义:二分图:\(G=(L,R,E)\),满足\(\forall(u,v)\inE\)都有\(u\inL,v\inR\)或\(u\inR,v\inL\)。可知“图中没有长度为奇数的环”是这个图是二分图的充分必要条件。图的匹配是一个\(E_m\subseteqE\)满足\(\nexistsi\inV(\text{当}G......
  • 如何处理TensorFlow中的InvalidArgumentError:数据类型不匹配
    如何处理TensorFlow中的InvalidArgumentError:数据类型不匹配......
  • Day1| 704. 二分查找 &27. 移除元素
    704.二分查找题目链接:https://leetcode.cn/problems/binary-search/description/思路:切记二分查找要基于排序好的数组或者数据,否则二分查找必不能使用!!!!!!!!!双指针写最简单,一个头指针从0开始,一个尾指针从数组长度-1开始,中间指针是头+尾/2,每次比较头尾中间指针的值......
  • 代码随想录算法训练营第一天 | 704. 二分查找、27. 移除元素
    704.二分查找这个之前有写过,最重要的就是把握住要去搜索的区间的形式,包括左闭右闭以及左闭右开两种classSolution{publicintsearch(int[]nums,inttarget){intleft=0,right=nums.length;while(left<right){//左闭右开的版本,结果存储......
  • 逻辑回归求解二分类问题以及SPSS的实现
    分类问题就是给出物质的属性,判断其属于什么成分,本文将讲述逻辑回归求解二分类问题本文着重于模型的实现,对于推导只是概括性的叙述目录一、问题提出二、逻辑回归函数logistic1.线性线性概率模型2.sigmod函数3.求解方法————极大似然估计4.分类原则三、SPSS实现————以水果......
  • 【转】【SQL】 实现左单一匹配
    原文地址:https://blog.csdn.net/weixin_46156257/article/details/131234451SQL的表连接中,如果主表中同一条数据对应被连接表有多条数据,则连接后数据会被扩大,但有时候我们希望数据不要被扩大,与主表中数据条数保持一致,即实现左单一匹配连接。假设我们有学生信息表TEST_TAB_STUDEN......
  • qoj5371 Matrix (二分图匹配)
    qoj5371Matrix二分图匹配判断无解的情况,当且仅当有\(a_{i,j}\)为负数或每一行和每一列的和不相同时无解。因为\(m\leN^2\),所以我们只需要每一次至少完成一个\(a_{i,j}\)即可。观察\(B\)矩阵的形成,实际上就是一个\(i\)行只能和一个\(j\)列匹配,跑二分图匹配即可。每......
  • 2000-2022年上市公司数字化转型与绿色创新质量匹配数据(含控制变量)
    2000-2022年上市公司数字化转型与绿色创新质量匹配数据(含控制变量)https://download.csdn.net/download/a519573917/89501000目录 上市公司数字化转型与绿色创新质量匹配的实证研究一、引言二、文献综述三、实证模型四、数据来源与描述性统计五、实证结果与分析六......
  • Nginx实现负载均衡的4种常用方式及路径匹配规则
    一、Nginx实现负载均衡的4种常用方式为:轮询模式、IP哈希模式、权重模式、最少连接实现负载均衡需要在http模块中配置使用upstream模块定义后台的webserver的池子,名为proxy-web,在池子中我们可以添加多台后台webserver,其中状态检查、调度算法都是在池子中配置;然后在se......
  • LeetCode 28题找出字符串中第一个匹配项的下标
    给你两个字符串 haystack 和 needle ,请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标(下标从0开始)。如果 needle 不是 haystack 的一部分,则返回  -1 。示例1:输入:haystack="sadbutsad",needle="sad"输出:0解释:"sad"在下标0和6......