題意: n個學生,m對關系,每一對互相認識的能住一個房間。問否把這些學生分成兩組,要求每組的學生都互不認識。求最多須要多少個房間。
能否分成兩組?也就是說推斷是不是二分圖,推斷二分圖的辦法,用 染色法
把初始點染成黑色,然后與之相連的染成白色,反復,使路徑黑白相間,
假設當前點的顏色和與他相連點的顏色同樣時,則說明這個圖不是二分圖
求最多須要多少個房間?也就是求最大匹配數。
#include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> #include <math.h> #define init(a) memset(a,0,sizeof(a)) #define PI acos(-1,0) using namespace std; const int maxn = 310; const int maxm = 100001; #define lson left, m, id<<1 #define rson m+1, right, id<<1|1 #define min(a,b) (a>b)?b:a #define max(a,b) (a>b)?a:b const int N = 50010; int ma[maxn][maxn]; int line[maxn],color[maxn]; bool vis[maxn]; int k,n,m; bool flag; int DFS(int u) { for(int v = 1;v<=n;v++) { if(ma[u][v]==1 && !vis[v]) { vis[v] = 1; if(line[v]==-1 || DFS(line[v])) { line[v] = u; return 1; } } } return 0; } void dfs(int u,int st) { if(flag == false) return ; for(int v = 1;v <= n;v++) { if(ma[u][v]) { if(!color[v]) { color[v]= -st;//黑染白 / 白染黑 dfs(v,color[v]); } else if(color[v]==st) { flag = false; return; } } } } bool judge() { flag = true; color[1] = 1 ;//1代表黑色,-1代表白色 dfs(1,1) ; return flag; } int K_M() { int ans = 0; memset(line,-1,sizeof(line)); for(int i = 1;i<=n;i++) { init(vis); ans += DFS(i); } return ans; } int main() { int a,b; while(scanf("%d%d",&n,&m)!=EOF) { init(ma); memset(color,0,sizeof(color)); for(int i = 1;i<=m;i++) { scanf("%d%d",&a,&b); ma[a][b] = 1; } if(!judge()) { puts("No"); continue; } int ans = K_M(); printf("%d\n",ans); } return 0; }
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索:z360901061

微信掃一掃加我為好友
QQ號聯系: 360901061
您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。
【本文對您有幫助就好】元
