hdu2444 染色法+二分图匹配

有n个关系，他们之间某些人相互认识。这样的人有m对。
你需要把人分成2组，使得每组人内部之间是相互不认识的。
如果可以，就可以安排他们住宿了。安排住宿时，住在一个房间的两个人应该相互认识。
最多的能有多少个房间住宿的两个相互认识。

首先题目是要问能不能分成两组，每组人之间互相不认识，每个人只与对面那部分的人认识。这个就是要判断是不是能构成一个二分图的样子。
判断二分图我们使用染色法，就是规定一个点的颜色，然后与其相连的点的颜色是不同的，如果遇到了无法满足的情况，（比如之前颜色是1 ， 但是到现在你又要这个点颜色是2就无法满足）。判断是二分图后，直接二分图匹配模板就可以了。还有个小问题就是，我们二分图匹配出来的数目要除以2,因为他是比如1和2匹配，2和1匹配算作了两种，所以答案去除以2就好了。
有任何问题尽管留言，我会尽量回复。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<time.h>
#include<cmath>
using namespace std;
const long long max_ = 1e3 + 7;
int tu[max_][max_];
int read()
{
	int s = 0, f = 1;
	char ch = getchar();
	while (ch<'0' || ch>'9') {
		if (ch == '-')
			f = -1;
		ch = getchar();
	}
	while (ch >= '0'&&ch <= '9') {
		s = s * 10 + ch - '0';
		ch = getchar();
	}
	return s * f;
}

int n, m, e, vis[max_], match[max_];
int dfs(int now) {
	for (int i = 1; i <= n; i++) {
		if (tu[now][i] && !vis[i]) {
			vis[i] = 1;
			if (match[i] == 0 || dfs(match[i])) {
				match[i] = now;
				return 1;
			}
		}
	}
	return 0;
}
int color[max_];
int bfs(int now) {
	queue<int>node;
	node.push(now);
	while (!node.empty()) {
		int tou = node.front();
		node.pop();
		for (int i = 1; i <= n; i++) {
			if (tu[tou][i] == 1) {
				if (color[i] == 0) {
					color[i] = (color[tou] == 1 ? 2 : 1);
					node.push(i);
				}
				else {
					if (color[i] == color[tou])return 0;
				}
			}
		}
	}
	return 1;
}
void qing() {
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			tu[i][j] = 0;
		}
		match[i] = 0;
		color[i] = 0;
	}
}
int main() {
	while (scanf_s("%d%d", &n,&m)!=EOF) {
		qing();
    while (m--) {
		int a = read(), b = read();
		tu[a][b] = 1;
		tu[b][a] = 1;
	}
	int sum = 0;
	color[1] = 1;
	if (!bfs(1)||n==1) { cout << "No" << endl; continue; }
	for (int i = 1; i <= n; i++) {
		memset(vis, 0, sizeof(vis));
		sum += dfs(i);
	}
	cout << sum/2 << endl;	
	}
	
	return 0;
}