传送门:http://acm.hdu.edu.cn/showproblem.php?pid=2444
题意:首先判断所有的人可不可以分成互不认识的两部分。如果可以分成 ,则求两部分最多相互认识的对数。
思路:二分图最大匹配问题。先BFS判断是否为二分图,再用匈牙利算法算最大匹配量
关于匈牙利算法:https://blog.csdn.net/CillyB/article/details/55511666
代码:
#include<iostream> #include<cstdio> #include<queue> #include<string.h> using namespace std; int map[205][205]; int vis[205]; int girl[205]; int n, m; int find(int x) { for(int y = 1; y <= n; y++) { if(map[x][y] && vis[y] == 0) { vis[y] = 1; if(girl[y] == 0 || find(girl[y])) { girl[y] = x; return 1; } } } return 0; } bool solve() { queue<int>q; q.push(1); vis[1] = 1; while(!q.empty()) { int x = q.front(); q.pop(); for(int i = 1; i <= n; i++) { if(map[x][i]) { if(vis[i] == 0) { if(vis[x] == 1) vis[i] = 2; else vis[i] = 1; q.push(i); } else if(vis[i] == vis[x]) return false; } } } return true; } int main() { while(~scanf("%d%d", &n, &m)) { for(int i = 1; i <= n; i++) { for(int j = 1; j <= n; j++) map[i][j] = map[j][i] = 0; vis[i] = 0; } for(int i = 1; i <= m; i++) { int a, b; scanf("%d%d", &a, &b); map[a][b] = map[b][a] = 1; } if(n == 1 || !solve()) { cout << "No" << endl; continue; } else { int ans = 0; memset(girl,0,sizeof(girl)); for(int i = 1; i <= n; i++) { memset(vis, 0, sizeof(vis)); ans += find(i); } cout << ans / 2 << endl; } } }