HDU - 3829 Cat VS Dog （最大独立集）
Cat VS DogTime Limit: 2000/1000 MS (Java/Others) Memory Limit: 125536/65536 K (Java/Others)Total Submission(s): 4539 Accepted Submission(s): 1670 Problem Description The zoo have N cats and M dogs, today there are P children visiting the zoo, each child has a like-animal and a dislike-animal, if the child's like-animal is a cat, then his/hers dislike-animal must be a dog, and vice versa.
Input The input file contains multiple test cases, for each case, the first line contains three integers N <= 100, M <= 100 and P <= 500.
Output For each case, output a single integer: the maximum number of happy children.
Sample Input 1 1 2 C1 D1 D1 C1 1 2 4 C1 D1 C1 D1 C1 D2 D2 C1
Sample Output 1 3 Hint Case 2: Remove D1 and D2, that makes child 1, 2, 3 happy.
Source |
每个人有喜欢的又不喜欢的，当他喜欢的留下，厌恶的走开始他会开心，问最多使多少人同时开心。
这样的话，应该对人进行二分，将喜欢及厌恶的两个人连表，求图的最大独立集就对了；
#include<cstdio>
#include<iostream>
#include<vector>
#include<cstring>
#include<string>
using namespace std;
vector<int>G[505];
bool vis[505];
int use[505];
struct ***
{
string love, hate;
}spt[505];
int n, m, p;
int find(int x) {
int sz = G[x].size();
for (int s = 0; s < sz; s++) {
int v = G[x][s];
if (!vis[v]) {
vis[v] = 1;
if (use[v] == 0 || find(use[v])) {
use[v] = x;
return 1;
}
}
}
return 0;
}
int main()
{
ios::sync_with_stdio(0);
while (cin >> n >> m >> p){
memset(use, 0, sizeof(use));
for (int s = 0; s <= p; s++) {
G[s].clear();
}
for (int s = 0; s < p; s++) {
cin >> spt[s].love >> spt[s].hate;
}
for (int s = 0; s < p; s++) {
for (int w = 0; w < p; w++) {
if (spt[s].hate == spt[w].love) {
G[s].push_back(w);
G[w].push_back(s);
}
}
}
int sum = 0;
for (int s = 0; s <= p; s++) {
memset(vis, 0, sizeof(vis));
if (find(s))sum++;
}
cout << p - (sum / 2) << '\n';
}
}
