加载中…HDU 3829 Cat VS Dog Multi-University_Training_Contest Host_By_HNU
(2011-07-13 11:21:27)
标签：
hdu3829catvsdog二分匹配it |
分类： 图论 |
题目描述：
p个人，n个猫，m个狗。p行输入，每行有i， j，表示这个人喜欢猫i，讨厌狗j，或者喜欢狗i，讨厌猫j。
现在扔掉一些动物，如果一个人讨厌的动物被扔掉了，喜欢的动物还在，他就很高兴。
问最多能让多少人高兴。
解题报告：
p个人分成两组：左边的人都是喜欢猫讨厌狗的，右边的人反之。
如果左边的i人和右边的j人冲突（i讨厌的狗是j喜欢的狗，或者j讨厌的猫是i喜欢的猫），就连接一条边。
这样问题转化成：从这个二分图中，找出最多的人，两两之间没有边（没有冲突，最大独立集）。
点数-二分匹配数就是最大独立集，就是答案。
代码如下：
for(int
i = 0; i < r; i++)
if (!vst[i]
&& g[u][i])
{
vst[i] = 1;
if (match[i] == -1 || find(match[i]))
{
match[i] =
u;
return
1;
}
}
return
0;
memset(match, -1, sizeof(match));
int ans
= 0;
for(int
i = 0; i < l; i++)
{
memset(vst, 0,
sizeof(vst));
ans += find(i);
}
return
ans;
while(scanf("%d%d%d", &n
,&m, &p) != EOF)
{
l = r = 0;
for(int i = 0; i
< p; i++)
{
string tmp1, tmp2;
cin >> tmp1
>> tmp2;
if (tmp1[0] == 'C')
{
a[l][0] =
tmp1;
a[l++][1] =
tmp2;
}
else
{
b[r][0] =
tmp1;
b[r++][1] =
tmp2;
}
}
memset(g, 0, sizeof(g)); int
cnt = 0;
for(int i = 0; i
< l; i++)
for(int j = 0; j < r; j++)
{
if (a[i][0]
== b[j][1] || a[i][1] == b[j][0])
g[i][j] = 1, cnt++;
}
printf("%d\n", p -
solve());
}
return
0;
p个人，n个猫，m个狗。p行输入，每行有i， j，表示这个人喜欢猫i，讨厌狗j，或者喜欢狗i，讨厌猫j。
现在扔掉一些动物，如果一个人讨厌的动物被扔掉了，喜欢的动物还在，他就很高兴。
问最多能让多少人高兴。
解题报告：
p个人分成两组：左边的人都是喜欢猫讨厌狗的，右边的人反之。
如果左边的i人和右边的j人冲突（i讨厌的狗是j喜欢的狗，或者j讨厌的猫是i喜欢的猫），就连接一条边。
这样问题转化成：从这个二分图中，找出最多的人，两两之间没有边（没有冲突，最大独立集）。
点数-二分匹配数就是最大独立集，就是答案。
代码如下：
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int n, m, p, g[500][500], l, r, vst[500], match[500];
string a[500][2], b[500][2];
int find(int u)
{
}
int solve()
{
}
int main()
{
}
喜欢
0
赠金笔