首页 > 其他分享 >二分图(例题)

二分图(例题)

时间:2024-05-12 17:08:53浏览次数:26  
标签:二分 const int bool quad 例题 col

    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());
  }

标签:二分,const,int,bool,quad,例题,col
From: https://www.cnblogs.com/0shadow0/p/18187958

相关文章

  • 洛谷 P2824 [HEOI2016/TJOI2016] 排序(二分,线段树)
    传送门解题思路据说是经典思路:把多次排序转化成二分+01序列。首先二分所求位置的数字是啥,将大于mid的数字变成1,将小于等于mid的数字变成0。这样在排序的时候就相当于统计区间里的1的个数(区间和),然后区间全部变成0或者1。也就是区间修改,区间求和,线段树可以实现。AC代码#inclu......
  • 匈牙利算法模板(二分图)
    booldfs(intnow){for(inti=h[now];i;i=nxt[i]){intt=to[i];//这里不用考虑会有回到父结点的边的问题//因为每次都是从左部找邻接点if(!vis[t]){vis[t]=true;//如果邻接点t是非匹配点,则找到一条增广路,匹配......
  • 加练日记2-二分,双指针,排序
    二分模板 #include<bits/stdc++.h>usingnamespacestd;usingll=longlong;constllMOD=998244353;lln,m;constllN=2e5+9;lla[N];llv[N];intf(llmid){ llans=0,pre=-1e9; for(inti=1;i<=n;i++){ if(a[i]-pre>=mid)ans++,pre=a[i......
  • 蓝桥杯-递增三元组(三种解法,二分, 双指针, 前缀和)
    给定三个整数数组A=[A1,A2,…AN],B=[B1,B2,…BN],C=[C1,C2,…CN],请你统计有多少个三元组(i,j,k)满足:1≤i,j,k≤NAi<Bj<Ck输入格式第一行包含一个整数N。第二行包含N个整数A1,A2,…AN。第三行包含N个整数B1,B2,…BN。第四行包含N个整数C1,C2,…CN。输出格......
  • 二分图
    1.二分图的概念二分图,又称二部图,英文名叫Bipartitegraph。如果一张无向图的\(N\(N≥2)\)个节点,可以分成A、B两个非空集合,其中\(A∩B=Φ\),并且在同一集合内的点之间都没有边相连,那么称这张无向图为一张二分图。A、B分别称为二分图的左部和右部。如下图所示。2.二......
  • 代码随想录算法训练营第第一天 | 704. 二分查找 、27. 移除元素
    704、二分查找题目链接:https://leetcode.cn/problems/binary-search/文章讲解:https://programmercarl.com/0704.二分查找.html视频讲解:https://www.bilibili.com/video/BV1fA4y1o715`varsearch=function(nums,target){letleft=0;letright=nums.length;letmi......
  • 代码随想录算法训练营第一天 | 704.二分查找 27.移除元素
    704.二分查找题目链接:https://leetcode.cn/problems/binary-search/文档讲解:https://programmercarl.com/0704.二分查找.html视频讲解:https://www.bilibili.com/video/BV1fA4y1o715左闭右开时间复杂度O(logn)空间复杂度O(1)classSolution{public:intsearch(......
  • 二分
    二分浮点数二分模板boolcheck(doublex){/*...*/}//检查x是否满足某种特性doublebsearch_3(doublel,doubler){constdoubleeps=1e-6;while(r-l>eps){doublemid=(l+r)/2;if(check(mid))r=mid;else......
  • 二分查找的个人朴素实用理解
    背景二分查找主要用于在有序数组中查找符合条件的特定值,更进一步可以拓展到查找大于特定值的最小数和小于特定值的最大数的边界值问题,在数据量很大的场景下合理利用有序或者说单调性这一特性大大提高查找效率,能在对数时间内解决问题。虽然理解起来很简单,但是二分法是很常用......
  • 二分法、冒泡排序
    【一】二分法二分法查找,也称为折半法,是一种在有序数组中查找特定元素的搜索算法思路:首先,从数组的中间元素开始搜索,如果该元素正好是目标元素,则搜索过程结束,否则执行下一步。如果目标元素大于/小于中间元素,则在数组大于/小于中间元素的那一半区域查找,然后重复步骤的操作。如......