3380 - 投票
小k同学正在玩一个游戏，在游戏中他扮演了一个马戏团的老板，现在小k同学需要利用马戏团中的A只猫和B只狗举办一次表演，表演之前他让观众进行了投票，投票的类容是：我想看到第号猫/狗的表演，不想看到第号猫/狗的表演。注意到每个观众都是更喜欢猫或更喜欢狗，所以两个空后面一定会被勾上不同的内容。喜欢猫的观众会在第一空后面选择猫，第二空后面选择狗；反之就会在第一空后面选择狗，第二空后面选择猫。对于每一个观众，只有当TA投票的内容都被满足了（即TA想看到的动物出场表演，TA不想看到的动物不参与表演）的时候，TA才会来看表演。当然啦，看表演是要付门票钱的，作为马戏团的老板，小k自然是希望来的人越多越好了。他想找到一个安排动物表演的方案，使得来看表演的观众尽量多。
Input
第1行3个正整数n、m、k，分别表示猫、狗和观众的数量
第2~k+1行，每行描述了一个观众的投票内容。
首先输入一个字符C或D紧接着是一个数字，表示某个观众想看到的动物，然后是一个空格隔开，接下去又是一个C或D加上一个数字，表示这个观众不想看到的动物，同一行中一定不会出现两个C或两个D。
<br />
<br />
【数据规模和约定】<span></span>
对于<span>25%</span>的数据，n,m≤<span>10,k</span>≤<span>25 ;</span>
对于<span>100%</span>的数据，n,m≤<span>300,k</span>≤<span>500.</span>
<br />
Output
输出一行一个正整数，表示小k在最优的安排下可以吸引多少观众来看表演
Examples
Input
1 2 4 C1 D1 C1 D1 C1 D2 D2 C1
Output
3
Solution C++
#include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <algorithm> #include <vector> using namespace std; const int MaxN = 505; int T, n, m, v; vector<int> e[MaxN]; bool c[MaxN]; int s[MaxN]; int love[2][MaxN]; int hate[2][MaxN]; bool dfs(int cur) { for (int k = 0; k < e[cur].size(); ++ k) if (c[e[cur][k]]) { c[e[cur][k]] = false; if (s[e[cur][k]] < 0 || dfs(s[e[cur][k]])) { s[e[cur][k]] = cur; return true; } } return false; } int main() { // freopen("vote.in", "r", stdin); // freopen("vote.out", "w", stdout); n = m = 0; scanf("%*d %*d %d", &v); for (int k = 1; k <= v; ++ k) { char ch; scanf(" %c", &ch); if (ch == 'C') { ++ n; scanf("%d %*c%d", &love[0][n], &hate[0][n]); } else { ++ m; scanf("%d %*c%d", &love[1][m], &hate[1][m]); } } for (int k = 1; k <= n; ++ k) e[k].clear(); for (int i = 1; i <= n; ++ i) for (int j = 1; j <= m; ++ j) if (love[0][i] == hate[1][j] || hate[0][i] == love[1][j]) e[i].push_back(j); memset(s, -1, sizeof(s)); int ans = 0; for (int k = 1; k <= n; ++ k) { memset(c, 1, sizeof(c)); if (dfs(k)) ++ ans; } printf("%d\n", v - ans); return 0; }