程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HDU 3829 Cat VS Dog

HDU 3829 Cat VS Dog

編輯：C++入門知識

HDU 3829 Cat VS Dog

題意：

p個人每個人有喜歡和討厭的動物如果選出的動物中包含這個人喜歡的動物同時不包含他討厭的動物那麼這個人會開心問最多幾個人開心

思路：

二分圖最大獨立集利用人與人之間的沖突建邊求最大匹配即可

注意：

題中的樣例給出動物的名字是D1、C1之類的其實名字可能比這個長… 所以數組開長點

代碼：

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
typedef unsigned long long LL;
#define N 510

struct edge {
	int v, next;
} ed[N * N];
int vis[N], match[N], head[N];
int n, tot;
char like[N][10], dislike[N][10];

void add(int u, int v) {
	ed[tot].v = v;
	ed[tot].next = head[u];
	head[u] = tot++;
}

bool dfs(int u) {
	int i, v;
	for (i = head[u]; ~i; i = ed[i].next) {
		v = ed[i].v;
		if (!vis[v]) {
			vis[v] = 1;
			if (!match[v] || dfs(match[v])) {
				match[v] = u;
				return true;
			}
		}
	}
	return false;
}

int bimatch() {
	int i, sol = 0;
	memset(match, 0, sizeof(match));
	for (i = 1; i <= n; i++) {
		memset(vis, 0, sizeof(vis));
		if (dfs(i))
			sol++;
	}
	return sol;
}

int main() {
	int i, j, ans;
	while (~scanf("%d%d%d", &i, &j, &n)) {
		for (i = 1; i <= n; i++)
			scanf("%s%s", like[i], dislike[i]);
		memset(head, -1, sizeof(head));
		tot = 0;
		for (i = 1; i <= n; i++) {
			for (j = i + 1; j <= n; j++) {
				if (!strcmp(like[i], dislike[j])
						|| !strcmp(like[j], dislike[i])) {
					add(i, j);
					add(j, i);
				}
			}
		}
		ans = n - bimatch() / 2;
		printf("%d\n", ans);
	}
	return 0;
}