首页 > 代码库 > HDU 3829 Cat VS Dog 【最大点独立集（建图比较好）】
HDU 3829 Cat VS Dog 【最大点独立集（建图比较好）】
大意：
有n只cat m只dog 有 k个熊孩子
每个熊孩子都有一个喜欢的动物 如果喜欢cat就必须讨厌dog 如果喜欢dag就必须讨厌cat
如果不喜欢的动物被移除而喜欢的未被移除那么这个熊孩子就会高兴
现在让你移除一些动物使得熊孩子高兴的人数最多，输出人数
分析：
如果对于cat与dog之间建边我们发现没法做
最后求得是熊孩子的数目
无非就是一个熊孩子开心一些熊孩子就会不高兴
也就是说熊孩子之间的高兴与不高兴存在着关系
那么把熊孩子当做点
如果两个熊孩子喜欢的动物存在冲突就建一条边
最后求最大点独立就可以了
代码：
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <vector> 5 using namespace std; 6 7 const int maxn = 505; 8 const int INF = 1000000000; 9 10 int vis[maxn];11 int Link[maxn];12 int n;13 vector<int> G[maxn];14 int Find(int u) {15 for(int i = 0; i < G[u].size(); i++) {16 int v = G[u][i];17 if(!vis[v]) {18 vis[v] = 1;19 if(Link[v] == -1 || Find(Link[v]) ) {20 Link[v] = u;21 return true;22 }23 }24 }25 return false;26 }27 28 int solve() {29 memset(Link, -1, sizeof(Link));30 int cnt = 0;31 for(int i = 1; i <= n; i++) {32 if(G[i].size() ) {33 memset(vis, 0, sizeof(vis));34 if(Find(i) ) cnt++;35 }36 }37 return cnt;38 }39 40 char s1[maxn][5], s2[maxn][5];41 bool check(int i, int j) {42 if(strcmp(s1[i], s2[j]) == 0 || strcmp(s2[i], s1[j]) == 0 ) {43 return true;44 }45 return false;46 }47 48 int main() {49 int x, y;50 while(EOF != scanf("%d %d %d",&x, &y, &n) ) {51 for(int i = 1; i <= n; i++) {52 scanf("%s %s", s1[i], s2[i]);53 }54 for(int i = 1; i <= n; i++) {55 G[i].clear();56 for(int j = 1; j <= n; j++) {57 if(i == j) continue;58 if(check(i, j) ) {59 G[i].push_back(j);60 }61 }62 }63 printf("%d\n",(2 * n - solve()) / 2);64 }65 return 0;66 }
HDU 3829 Cat VS Dog 【最大点独立集（建图比较好）】
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。