二分图（例题）

· 浏览次数 : 0

小编点评

The code is an implementation of the Hungarian algorithm to determine the maximum number of connected components in a given graph. **Key Concepts:** * **Hungarian Algorithm:** An algorithm to find the maximum number of connected components in a graph. * **Graph:** A collection of connected vertices. * **Connected Component:** A group of vertices where any two vertices are connected by an edge. * **Component:** A group of connected vertices that form a subset of the graph. **Algorithm Steps:** 1. **Input:** - Read the input data, including the number of vertices in the graph, the graph itself (represented as a string), and the maximum edge weight. 2. **Initialization:** - Initialize a 2D vector `match` to keep track of which vertices belong to which component. - Initialize an array of vectors `s` to store the components of the graph. 3. **Depth-First Search (DFS):** - For each vertex in the graph, perform a DFS to find all its connected vertices. - For each connected vertex, update the `match` array to indicate that it belongs to the same component as the current vertex. 4. **Counting Connected Components:** - After completing the DFS, count the number of components by counting the number of elements in the `match` array that are set to 1. 5. **Output:** - Print the number of connected components found in the graph. **Additional Notes:** * The code uses a 2D array `s` to represent the graph, where `s[i][j]` represents whether vertex `i` is connected to vertex `j`. * The code assumes that the graph is connected and has no cycles. * The time complexity of the algorithm is O(V + E), where V is the number of vertices and E is the number of edges in the graph.

正文

    https://www.cnblogs.com/kuangbiaopilihu/p/18184536

$\quad $ 这里不再介绍二分图的基础知识，只是一些例题的解释。

$\quad $ 当然，这道题可以用二分+并查集来解决。但这是二分图专辑，所以介绍一下二分图做法。
$\quad $ 首先如果两个罪犯之间有仇恨，那么当他们不在同一所监狱时不会发生冲突。若要若干个罪犯之间不产生冲突，那么将有仇恨的罪犯连边，则不会发生冲突的罪犯恰好形成一个二分图。
$\quad $ 所以按照有仇恨罪犯之间的怒气值排序，再二分一下答案下标，把边权大于二分答案的边加进去，如果形成了一个二分图，则答案合法。然后便可得出答案。

点击查看代码 
  #include<bits/stdc++.h>
  using namespace std;
  const int N=1e5+100;
  vector<int> sl[N];
  struct stu{
      int x,y,w;
  }s[N];
  int col[N],n,m,ans;
  bool is_gragh(int cur,int fa,int color){
      col[cur]=color;
      for(int i=0;i<sl[cur].size();i++){
          int y=sl[cur][i];
          if(col[y]==color)return false;
          if(col[y]==0&&!is_gragh(y,cur,3-color))return false;
      }
      return true;
  }
  bool check(int x){
      for(int i=1;i<=n;i++)sl[i].clear();
      memset(col,0,sizeof col);
      for(int i=x+1;i<=m;i++){
          int x=s[i].x,y=s[i].y;
          sl[x].push_back(y);
          sl[y].push_back(x);
      }
      for(int i=1;i<=n;i++)if(col[i]==0)if(!is_gragh(i,0,1))return false;
      return true;
  }
  bool cmp(stu a,stu b){return a.w<b.w;}
  int main(){
      scanf("%d%d",&n,&m);
      for(int i=1;i<=m;i++)scanf("%d%d%d",&s[i].x,&s[i].y,&s[i].w);
      sort(s+1,s+1+m,cmp);
      int l=0,r=m;
      while(l<=r){
          int mid=(l+r)>>1;
          if(check(mid))r=mid-1,ans=mid;
          else l=mid+1;
      }
      printf("%d",s[ans].w);
      return 0;
  }

$\quad $ 可以发现，如果选择了一列，那么处于这一列的点将都被消除，那么就可以将该点与其所在行与所在列相连，以表示其关联。先拿样例举例：

$\quad $ 我们发现，点只存在于行和列之间的边上，那么将点省去，可以得到一个二分图。这样问题就变为了一个二分图的点最大覆盖问题，求最大匹配即可。

点击查看代码 


  #include<bits/stdc++.h>
  using namespace std;
  const int N=1e4+100;
  bool vis[N];
  int n,k,match[N];
  vector<int> s[N<<1];
  bool dfs(int x){
      for(int i=0;i<s[x].size();i++){
          int y=s[x][i];
          if(!vis[y]){
              vis[y]=1;
              if(!match[y]||dfs(match[y])){
                  match[y]=x;
                  return true;
              }
          }
      }
      return false;
  }
  int Hungary(){
      int ans=0;
      for(int i=1;i<=n;i++){
          memset(vis,0,sizeof vis);
          if(dfs(i))ans++;
      }
      return ans;
  }
  int main(){
      scanf("%d%d",&n,&k);
      n<<=1;
      for(int i=1;i<=k;i++){
          int x,y;
          scanf("%d%d",&x,&y);
          y+=n;
          s[x].push_back(y);
          s[y].push_back(x);
      }
      printf("%d",Hungary());
      return 0;
  }

$\quad $ 还是先膜样例，这里用汉字表示锦囊，阿拉伯数字表示题目。

$\quad $ 同样可以得到一张二分图，只不过这道题不是要求最大匹配，因为答题出现错误就淘汰了，仔细观察匈牙利算法代码，可以发现他正是从1顺序开始寻找的，所以我们只要在无法匹配时打断循环即可。

点击查看代码 


  #include<bits/stdc++.h>
  using namespace std;
  const int N=1e4+100;
  bool vis[N];
  int n,k,match[N];
  vector<int> s[N<<1];
  bool dfs(int x){
      for(int i=0;i<s[x].size();i++){
          int y=s[x][i];
          if(!vis[y]){
              vis[y]=1;
              if(!match[y]||dfs(match[y])){
                  match[y]=x;
                  return true;
              }
          }
      }
      return false;
  }
  int Hungary(){
      int ans=0;
      for(int i=1;i<=n;i++){
          memset(vis,0,sizeof vis);
          if(dfs(i))ans++;
          else break;
      }
      return ans;
  }
  int main(){
      scanf("%d%d",&n,&k);
      for(int i=1;i<=k;i++){
          int x,y;
          scanf("%d%d",&x,&y);
          x++,y++;
          s[i].push_back(y);
          s[i].push_back(x);
      }
      printf("%d",Hungary());
      return 0;
  }

$\quad $ 先求出所有小衫到所有出口所需时间，对时间小于k的情况，就将两者相连，最后还是的到一张二分图，此时只需要求出最大匹配即可。
注意开double！！

点击查看代码 
  #include<bits/stdc++.h>
  using namespace std;
  const int N=1e4+100;
  bool vis[N];
  int n,k,match[N],m;
  vector<int> s[N<<1];
  double x[N],y[N];
  bool dfs(int x){
      for(int i=0;i<s[x].size();i++){
          int y=s[x][i];
          if(!vis[y]){
              vis[y]=1;
              if(!match[y]||dfs(match[y])){
                  match[y]=x;
                  return true;
              }
          }
      }
      return false;
  }
  int Hungary(){
      int ans=0;
      for(int i=1;i<=m;i++){
          memset(vis,0,sizeof vis);
          if(dfs(i))ans++;
      }
      return ans;
  }
  int main(){
      scanf("%d%d%d",&m,&n,&k);
      //m是小衫个数，n是点数，k是边权最大值。
      for(int i=1;i<=n;i++)scanf("%lf%lf",&x[i],&y[i]);
      for(int i=1;i<=m;i++){
          double xl,yl,vl,tl;
          scanf("%lf%lf%lf",&xl,&yl,&vl);
          for(int j=1;j<=n;j++){
              tl=sqrt((x[j]-xl)*(x[j]-xl)+(y[j]-yl)*(y[j]-yl));
              tl/=vl;
              // cout<<tl<<endl;
              if(k>=tl)s[i].push_back(j+m),s[j+m].push_back(i);
          }
      }
      printf("%d",Hungary());
      return 0;
  }

$\quad $ 这道题和穿越小行星群很像，但是有石头阻拦，对于有石头阻拦的，我们可以将一行视为两行、一列视为两列，再将合法的位置与其行列连边。这样又得到一张二分图，再求最大匹配即可。

点击查看代码 
#inclu  de<bits/stdc++.h>
  using namespace std;
  const int N=65;
  char ch[N*N][N*N];
  bool vis[N*N];
  int n,m,match[N*N],row[N*N][N*N],col[N*N][N*N];
  int ntot,ltot;
  vector<int>s[N*N];
  bool dfs(int x){
      for(int i=0;i<s[x].size();i++){
          int y=s[x][i];
          if(!vis[y]){
              vis[y]=1;
              if(!match[y]||dfs(match[y])){
                  match[y]=x;
                  return true;
              }
          }
      }
      return false;
  }
  int Hungary(){
      int ans=0;
      for(int i=1;i<=ntot;i++){
          memset(vis,0,sizeof vis);
          if(dfs(i))ans++;
      }
      return ans;
  }
  int main(){
      scanf("%d%d",&m,&n);
      for(int i=1;i<=m;i++)scanf("%s",ch[i]+1);
      for(int i=1;i<=m;i++){
          for(int j=1;j<=n;j++){
              if(ch[i][j]-'#'){
                  if(j>1&&ch[i][j-1]-'#')row[i][j]=row[i][j-1];
                  else row[i][j]=++ntot;
                  if(i>1&&ch[i-1][j]-'#')col[i][j]=col[i-1][j];
                  else col[i][j]=++ltot;
              }

          }
      }
      for(int i=1;i<=m;i++){
          for(int j=1;j<=n;j++){
              if(ch[i][j]=='o')s[row[i][j]].push_back(col[i][j]+ntot);
          }
      }
      printf("%d",Hungary());
  }

与二分图（例题）相似的内容：

二分图（例题）

https://www.cnblogs.com/kuangbiaopilihu/p/18184536 $\quad $ 这里不再介绍二分图的基础知识，只是一些例题的解释。 $\quad $ 当然，这道题可以用二分+并查集来解决。但这是二分图专辑，所以介绍一下二分图做法。 $\quad $ 首先如果两

0
算法学习笔记(3): 倍增与ST算法

倍增 目录倍增查找 洛谷P2249重点变式练习快速幂ST表扩展 - 运算扩展 - 区间变式答案倍增更多的用法优化矩形查询优化建图优化 DP作者有话说 倍增，字面意思即”成倍增长“ 他与二分十分类似，都是基于”2“的划分思想 那么具体是怎么样，我们以一个例子来看 查找 洛谷P2249 依据题面，我们知

算法 学习 笔记 倍增
81
设计模式学习（二）工厂模式——工厂方法模式+注册表

目录工厂方法模式的瑕疵注册表 工厂方法模式的瑕疵 在前一篇笔记中我们介绍了工厂方法模式，示例的类图如下： 考虑一种情况：现在要在程序运行时，根据外部资源，动态的实例化对象。也就是说在编译期我们无法知道要实例化的对象的类型。因此在实例化的过程中，就需要加以判断。 例如，在我的例子中，要根据连接到主机的

0
WPF网格类型像素着色器

由于WPF只能写像素着色器，没法写顶点着色器，所以只能在这上面做文章了 刚好有个纹理坐标TEXCOORD输入可用，而且值的范围是已知的0-1，左上角是原点，这就好办了 例子 索引 二分网格 使用ceil 0-1移动定义域到-0.5 - 0.5，然后向上取整变成 0 / 1 float4 main(f

wpf
0
二分查找 | C++

以此题为例：P2249 【深基13.例1】查找 二分查找 对于一个单调不降的序列 \(S\)，传统查找的复杂度是 \(O(|S|)\)，即 \(O(n)\). 有时候序列 \(S\) 中的元素特别多，或者你希望尽量减小复杂度，那么，有没有复杂度更低的方法呢？ 理论上是不行的，因为读入的复杂度已经达到

3
「网络流浅谈」最大流的应用

二分图匹配 考虑如何将二分图匹配问题，转化为流网络。设置 \(1\) 个汇点和源点，从源点向二分图一侧的每一个点连边，从另一侧向汇点连边，边权均为 \(1\)，二分图中的边也全部加入，权值设为 \(1\)。这样，二分图的最大匹配等于流网络的最大流。 P2756 飞行员配对方案问题 题意：给定 \(1

5
算法学习笔记(7): 二分图

# 二分图 [TOC] > Bipartite graph, 又称二部图 **定义**：如果一张无向图的$N$个节点可以分成两个没有相同点的非空集合$A$, $B$,且存在一种分法使得同一个集合内的点没有相连的边，那么这个图为**二分图**，$A$, $B$, 分别为此二分图的左部和右部。 **判定

算法 学习 笔记 二分
54
杂题选讲 #1：二分图边着色

Vizing 定理 定义 考虑如下的问题：对一个无向图的边进行着色，要求相邻的边染不同种颜色。问 需要的最少的颜色数是多少。 解决上述问题需要借助 Vizing 定理（又称维金定理）。 在开始之前，我们先进行一些符号的规定。 \(\Delta(G)\)：无向图 \(G=(V,E)\) 的最大度数，即

3
高一下三调模拟赛5.13（附关于二分图匈牙利建边的详细思考）

前言注：本篇为知识性内容，A题附详解关于匈牙利算法求最大独立子集难以理解的建边问题的思考，若有不当之处感谢指出。暂时只写了A篇题解，以供帮助大家理解相关问题，剩余题解会进行补充。 又是小集训的一周，总要伴随着模拟赛... 还是五道题目： A. 攻击装置 B. 循环 C. 漫步 D. 穿越 E. 结队

2
股债二八平衡策略

更多精彩内容，欢迎关注公众号：数量技术宅，也可添加技术宅个人微信号：sljsz01，与我交流。 雪球蛋卷二八安睡策略 雪球旗下的蛋卷基金，曾经推出过一个名为二八安睡策略的组合基金，绩效极为很稳定，如图： 二八安睡策略的组合基金的投资逻辑 a. 投资者购买“蛋卷安睡二八平衡”视同投资者接受约定交易业务

二八 平衡 策略
118
# 热门排行
微软 New Bing AI 申请与使用保姆级教程（免魔法） ChatGPT API使用介绍 ChatGPT开发实战 一篇带你了解如何使用纯前端类Excel表格构建现金流量表 手把手教你玩转 Excel 数据透视表 为什么 C# 可能是最好的第一编程语言 .NET 入门到高级路线 提高工作效率的神器：基于前端表格实现Chrome Excel扩展插件 React + Springboot + Quartz，从0实现Excel报表自动化 用Echarts实现前端表格引用从属关系可视化
© PmDaddy. 2023 PmDaddy教程网 All rights reserved.