int main() {
int k, i, j, x, y;
while(scanf("%d%d%d", &n, &m, &k) != -1 && n) {
for(i = 1;i <= n; i++)
for(j = 1;j <= m; j++)
mp[i][j] = 0;
while(k--) {
scanf("%d%d", &x, &y);
mp[x][y] = 1;
}
int ans = 0;
for(i = 1;i <= m; i++) match[i] = 0;
for(i = 1;i <= n; i++) {
for(j = 1;j <= m; j++) vis[j] = 0;
if(dfs(i)) ans++;
}
printf("%d", ans);
for(i = 1;i <= n; i++) markl[i] = markr[i] = right[i] = 0;
for(i = 1;i <= m; i++) if(match[i])
right[match[i]] = i;
for(i = 1;i <= m; i++) if(!match[i]){
findmin(i);
}
//左边标记过的匹配点
for(i = 1;i <= n; i++) if(markl[i]) printf(" r%d", i);
//右边未标记的匹配点
for(i = 1;i <= m; i++) if(match[i] && !markr[i])　 printf(" c%d", i); puts("");
}
return 0;
}

UVa 12083 - Guardian of Decency

最大独立集，根据男女划分为二分图，求最大匹配数，结果就是总数减去最大匹配数。
wrong answer注意有一个地方，身高的条件不是至少相差40厘米，而是身高相差大于40厘米。

[html]
/* **********************************************
Author : JayYe
Created Time: 2013-8-18 13:26:39
File Name : zzz.cpp
*********************************************** */

#include
#include
#include
using namespace std;

const int maxn = 500+5;

struct PP {
int h;
char music[111],sport[111];
}boy[maxn], girl[maxn], tmp;

int n, m, match[maxn];
bool vis[maxn], mp[maxn][maxn];

bool dfs(int i) {
for(int j = 1;j <= m; j++) if(mp[i][j] && !vis[j]) {
vis[j] = 1;
if(!match[j] || dfs(match[j])) {
match[j] = i;
return true;
}
}
return false;
}

char sex[2], music[111], sport[111];
int main() {
int t, i, j;
scanf("%d", &t);
while(t--) {
scanf("%d", &n);
int n1 = 0, n2 = 0, h;
for(i = 1;i <= n; i++) {
scanf("%d%s%s%s", &tmp.h, sex, tmp.music, tmp.sport);
if(sex[0] == 'M') boy[++n1] = tmp;
else girl[++n2] = tmp;
}
n = n1, m = n2;
for(i = 1;i <= n; i++) {
for(j = 1;j <= m; j++) {
if(abs(boy[i].h - girl[j].h) <= 40 && strcmp(boy[i].music, girl[j].music) == 0 && strcmp(boy[i].sport, girl[j].sport) != 0) {
mp[i][j] = 1;
}
else
mp[i][j] = 0;
}
}
for(i = 1;i <= m; i++) match[i] = 0;
int ans = 0;
for(i = 1;i <= n; i++) {
for(j = 1;j <= m; j++) vis[j] = 0;
if(dfs(i)) ans++;
}
printf("%d\n", n+m-ans);
}
return 0;
}

/* **********************************************
Author : JayYe
Created Time: 2013-8-18 13:26:39
File Name : zzz.cpp
*********************************************** */

#include
#include
#include
using namespace std;

const int maxn = 500+5;

struct PP {
int h;
char music[111],sport[111];
}boy[maxn], girl[maxn], tmp;

int n, m, match[maxn];
bool vis[maxn], mp[maxn][maxn];

bool dfs(int i) {
for(int j = 1;j <= m; j++) if(mp[i][j] && !vis[j]) {
vis[j] = 1;
if(!match[j] || dfs(match[j])) {
match[j] = i;
return true;
}
}
return false;
}