首页 > 代码库 > HDU 3829 Cat VS Dog
HDU 3829 Cat VS Dog
题意:
p个人 每个人有喜欢和讨厌的动物 如果选出的动物中包含这个人喜欢的动物同时不包含他讨厌的动物那么这个人会开心 问 最多几个人开心
思路:
二分图最大独立集 利用人与人之间的冲突建边 求最大匹配即可
注意:
题中的样例给出动物的名字是D1、C1之类的 其实名字可能比这个长… 所以数组开长点
代码:
#include<cstdio> #include<iostream> #include<cstring> #include<string> #include<algorithm> #include<map> #include<set> #include<vector> #include<queue> #include<cstdlib> #include<ctime> #include<cmath> 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; }
HDU 3829 Cat VS Dog
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。