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 }
