#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<iostream>
#include<vector>
#include<queue>
#include<cmath>
using namespace std;
#define INF 0x3fffffff
#define maxn 505
int n, m, p, P[maxn], color[maxn];///n只猫 m只狗 p个人
bool G[maxn][maxn], vis[maxn];///构图
vector<vector<int> > LikeDog;///喜欢第k只狗的人邻接表
vector<vector<int> > DisDog;///不喜欢这只够的人的集合
vector<vector<int> > LikeCat;///同上
vector<vector<int> > DisCat; void Init()
{
LikeDog.clear();
LikeDog.resize(m+);
LikeCat.clear();
LikeCat.resize(n+); DisDog.clear();
DisDog.resize(m+);
DisCat.clear();
DisCat.resize(n+);
memset(G, false, sizeof(G) );
} void MakeMap()
{
for(int i=; i<=m; i++)
{
int len1 = LikeDog[i].size();
int len2 = DisDog[i].size();
for(int j=; j<len1; j++)
{
int v1 = LikeDog[i][j];
for(int k=; k<len2; k++)
{
int v2 = DisDog[i][k];
G[v1][v2] = true;
G[v2][v1] = true;
}
}
} for(int i=; i<=n; i++)
{
int len1 = LikeCat[i].size();
int len2 = DisCat[i].size();
for(int j=; j<len1; j++)
{
int v1 = LikeCat[i][j];
for(int k=; k<len2; k++)
{
int v2 = DisCat[i][k];
G[v1][v2] = true;
G[v2][v1] = true;
}
}
}
}
bool Find(int u)
{
for(int i=; i<=p; i++)
{
if(!vis[i] && G[u][i])
{
vis[i] = true;
if(P[i] == - || Find(P[i]) )
{
P[i] = u;
return true;
}
}
}
return false;
}
void DFS(int u,int Color)
{
color[u] = Color;
for(int i=; i<=p; i++)
{
if(G[u][i] && !color[i])
{
DFS(i, -Color);
}
}
} int solve()
{
int ans = ;
memset(P, -, sizeof(P));
memset(color, , sizeof(color)); for(int i=; i<=p; i++)
{
if(color[i] == )
DFS(i, );
}
for(int i=; i<=p; i++)
{
memset(vis, false, sizeof(vis));
if(color[i] == && Find(i) )
ans ++;
}
return p - ans;
} int main()
{
while(scanf("%d %d %d ",&n, &m, &p) != EOF)
{
char ch1, ch2;
int a, b;
Init();
for(int i=; i<=p; i++)
{
scanf("%c%d %c%d",&ch1, &a, &ch2, &b);
getchar();
if(ch1 == 'C')
{
LikeCat[a].push_back(i);
DisDog[b].push_back(i);
}
else
{
LikeDog[a].push_back(i);
DisCat[b].push_back(i);
}
}
MakeMap();
printf("%d\n", solve() );
}
return ;
}
HDU 3829 Cat VS Dog(最大独立集)的更多相关文章
-
HDU 3829 Cat VS Dog (最大独立集)【二分图匹配】
<题目链接> 题目大意: 动物园有n条狗.m头猫.p个小孩,每一个小孩有一个喜欢的动物和讨厌的动物.如今动物园要转移一些动物.假设一个小孩喜欢的动物在,不喜欢的动物不在,他就会happy. ...
-
HDU 3829 Cat VS Dog / NBUT 1305 Cat VS Dog(二分图最大匹配)
HDU 3829 Cat VS Dog / NBUT 1305 Cat VS Dog(二分图最大匹配) Description The zoo have N cats and M dogs, toda ...
-
HDU 3829——Cat VS Dog——————【最大独立集】
Cat VS Dog Time Limit:1000MS Memory Limit:65536KB 64bit IO Format:%I64d & %I64u Submit S ...
-
hdu 3829 Cat VS Dog 二分图匹配 最大点独立集
Cat VS Dog Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 125536/65536 K (Java/Others) Prob ...
-
HDU 3829 - Cat VS Dog (二分图最大独立集)
题意:动物园有n只猫和m条狗,现在有p个小孩,他们有的喜欢猫,有的喜欢狗,其中喜欢猫的一定不喜欢狗,喜欢狗的一定不喜欢猫.现在管理员要从动物园中移除一些动物,如果一个小孩喜欢的动物留了下来而不喜欢的动 ...
-
HDU - 3829 Cat VS Dog (二分图最大独立集)
题意:P个小朋友,每个人有喜欢的动物和讨厌的动物.留下喜欢的动物并且拿掉讨厌的动物,这个小朋友就会开心.问最多有几个小朋友能开心. 分析:对于每个动物来说,可能既有人喜欢又有人讨厌,那么这样的动物实际 ...
-
hdu 3829 Cat VS Dog 二分匹配 最大独立点集
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3829 题目大意: 给定N个猫,M个狗,P个小朋友,每个小朋友都有喜欢或者不喜欢的某猫或者某狗 管理员从 ...
-
HDU 3829 Cat VS Dog
题意: p个人 每一个人有喜欢和讨厌的动物 假设选出的动物中包括这个人喜欢的动物同一时候不包括他讨厌的动物那么这个人会开心 问 最多几个人开心 思路: 二分图最大独立集 利用人与人之间的冲突 ...
-
hdu 2768 Cat vs. Dog 最大独立集 巧妙的建图
题目分析: 一个人要不是爱狗讨厌猫的人,要不就是爱猫讨厌狗的人.一个人喜欢的动物如果离开,那么他也将离开.问最多留下多少人. 思路: 爱猫和爱狗的人是两个独立的集合.若两个人喜欢和讨厌的动物是一样的, ...
随机推荐
-
解决Spring的Component-scan和packagesToScan不支持Eclipse RCP问题
http://www.360doc.com/content/13/0401/13/10825198_275274565.shtml
-
进程间通信方式与Binder机制原理
1, Intent隐式意图携带数据 2, AIDL(Binder) 3, 广播BroadCast 4, 内容提供者ContentProvider --------------------------- ...
-
网站配置好了,在本地能登录系统,但是挂在IIS上就无法登录了,提示数据库连接错误
我用的VS2010开发的网站,但是挂在本机的IIS上的时候就无法登录了,提示错误如下:
-
CentOS6.4 配置LVS(DR模式)
DR模式中LVS主机与实际服务器都有一块网卡连在同一物理网段上. IP分配 VIP:10.10.3.170 RIP1:10.10.3.140 RIP2:10.10.3.141 1.安装所需的依赖包 y ...
-
Android NDK开发(五)--C代码回调Java代码【转】
转载请注明出处:http://blog.csdn.net/allen315410/article/details/41862479 在上篇博客里了解了Java层是怎样传递数据到C层代码,并且熟悉了大部 ...
-
memory model
最近看C++11 atomic发现对memory_order很是不理解,memory_order_relaxed/memory_order_consume/memory_order_acquire/m ...
-
打造简单实用的Thinkphp分页样式(Bootstrap版本)
先吐槽一下ThinkPHP3.1版的分页样式,虽然看起来也很简单大方,但是所有的页码全是使用简单的数字,之间的空隙比较小,不大容易点,还有那个“前5页”和“后5页”显得有点多余,因为点击当前显示第一页 ...
-
SharePoint 2007 (MOSS/WSS) - how to remove ";Download a Copy"; context menu from a Document Library
One of my friend and colleague asked me this question. I found it tricky and a good post for my blog ...
-
小随笔:利用Shader实现模型爆炸和沙粒化的效果
0x00 前言 上一篇小随笔<小随笔:利用Shader给斯坦福兔子长毛和实现雪地效果>中,我和大家聊了聊著名的斯坦福兔子和利用geometry shader实现的一些效果.这篇文章继续沿用 ...
-
linkin大话设计模式--抽象工厂
linkin大话设计模式--抽象工厂 在前面讲到的简单工厂里面虽然实现了我们那个类和其中的依赖的解耦,但是在产生我们需要的依赖的那个工厂里面还是和具体的产品类耦合了 现在要是还想彻底解耦的话怎么办呢 ...