20211011二分图匹配+判定
- 2021 年 10 月 11 日
- 笔记
今天又是摸鱼的一天，就复习了一下数据结构，然后树剖板子打炸了，线段树2调疯了，tarjan也搞没了。
还有就是学了一下二分图，之前假期发了学案懒得看，今天就跑过去听，感觉还不错。
1.二分图是什么：
二分图又称作二部图，是图论中的一种。 设G=(V,E)是一个无向图，如果顶点V可分割为两个互不相交的子集(A,B)，并且图中的每条边（i，j）所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A,j in B)，则称图G为一个二分图。
简单来说，就是能把定点分成两部分，任意两点间有且只有一条路径。
至于二分图的判定，我们用深度搜索染色来实现。
1 #include<bits/stdc++.h> 2 using namespace std; 3 4 int n,m,color[205]; 5 vector<int> node[205];//领接表存图 6 7 bool dfs(int v,int c){//搜索染色 8 color[v]=c; 9 for(int i=0;i<node[v].size();i++){ 10 if(color[node[v][i]]==c){//相连的点颜色必须不同 11 return 0; 12 }else if(color[node[v][i]]==0&&!dfs(node[v][i],-c)){//还未染色切染了色也没有问题 13 return 0; 14 } 15 } 16 return 1; 17 } 18 int main(){ 19 int u,v; 20 cin>>n>>m; 21 for(int i=0;i<m;i++){ 22 cin>>u>>v; 23 node[u].push_back(v); 24 node[v].push_back(u); 25 } 26 27 for(int i=0;i<n;i++){ 28 if(color[i]==0){//从每一个点开始 29 if(!dfs(i,1)){ 30 cout<<"NO"<<endl; 31 return 0; 32 } 33 } 34 } 35 cout<<"YES"<<endl; 36 37 38 return 0; 39 }
例题：关押罪犯//www.luogu.com.cn/problem/P1525
思路：二分答案+染色搜索判定
先排序按照暴力事件的大小升序排列，然后二分一个答案，如果MID满足条件那么大于mid的都可以，接下来就向左半边二分。
我们每找到一个mid的值就用一个check函数判断是否合法。判断方式就是，把大于mid的边存入领接表，再用染色判断大于他的边能否形成一个二分图。
代码：
1 #include<bits/stdc++.h> 2 using namespace std; 3 4 const int N=20010; 5 const int M=100010; 6 int n,m,color[N]; 7 bool flag; 8 vector<int> e[N]; 9 struct edges{ 10 int x,y,v; 11 }a[M]; 12 13 bool cmp(edges a,edges b){ 14 return a.v<b.v; 15 } 16 17 //void dfs(int u,int c){ 18 // color[u]=c; 19 // for(int i=0;i<e[i].size();i++){ 20 // int v=e[u][i]; 21 // if(!color[v]){ 22 // dfs(v,-c); 23 // }else 24 // if(color[v]==c){ 25 // flag=0; 26 // } 27 // } 28 //} 29 void dfs(int u, int c) //染色 30 { 31 color[u]=c; 32 for(int i=0;i<e[u].size();i++) //枚举从u出 33 { 34 int v=e[u][i]; //v是u的相邻 35 if(!color[v]) dfs(v,-c); //继续染色 36 else if(color[v]==c) flag=false; //颜色 37 } 38 } 39 40 41 //bool check(int pos){ 42 // for(int i=1;i<=n;i++) e[i].clear(); 43 // for(int i=pos+1;i<=m;i++){ 44 // e[a[i].x].push_back(a[i].y); 45 // e[a[i].y].push_back(a[i].x); 46 // } 47 // flag=true; 48 // memset(color,0,sizeof(color)); 49 // for(int i=1;i<=n;i++){ 50 // if(!color[i]){ 51 // dfs(i,1); 52 // if(!flag) return false; 53 // } 54 // } 55 // return true; 56 //} 57 58 bool check(int pos) //判断是否合法：能构成 59 { 60 for(int i=1;i<=n;i++) e[i].clear(); // 61 for(int i=pos+1;i<=m;i++) // 62 { 63 e[a[i].x].push_back(a[i].y); 64 e[a[i].y].push_back(a[i].x); 65 } 66 flag=true; 67 memset(color,0,sizeof color); 68 for(int i=1;i<=n;i++) // 69 if(!color[i]) 70 { 71 dfs(i,1); 72 if(!flag) return false; 73 } 74 return true; 75 } 76 int main() 77 { 78 cin>>n>>m; 79 for(int i=1;i<=m;i++){ 80 cin>>a[i].x>>a[i].y>>a[i].v; 81 } 82 sort(a+1,a+m+1,cmp); 83 84 int l=0; 85 int r=m; 86 int mid; 87 // while(l<r){ 88 // mid=(l+r)>>1; 89 // if(check(mid)){ 90 // r=mid; 91 // cout<<r<<' '<<123<<endl; 92 // }else l=mid+1,cout<<l<<' '<<321<<endl; 93 // } 94 while(l<r) 95 { 96 mid=(l+r)>>1; 97 if(check(mid)) 98 r=mid; 99 else 100 l=mid+1; 101 } 102 if(m==1){ 103 cout<<0<<endl; 104 } else{ 105 106 cout<<a[l].v<<endl; 107 } 108 return 0; 109 }
