HDU 2768 Cat vs Dog(最大獨立集)

[cpp] 
/*
題意：喜歡或者討厭同一只貓和狗的人不能同時留下
題解：將觀眾分成兩組，左邊是喜歡貓的，右邊是喜歡狗的，如果存在沖突，則在這兩個觀眾之間加一條邊，於是問題轉換成求最大獨立集問題。
*/ 
 
#include <iostream> 
using namespace std; 
const int nMax = 505; 
struct Node 
{ 
    char str1[10]; 
    char str2[10]; 
}cat[nMax], dog[nMax]; 
int cat_num, dog_num; 
int map[nMax][nMax]; 
int useif[nMax]; 
int link[nMax]; 
int c, d, v; 
 
int can(int t) 
{ 
    for(int i = 0; i < dog_num; ++ i) 
    { 
        if(!useif[i] && map[t][i]) 
        { 
            useif[i] = 1; 
            if(link[i] == -1 || can(link[i])) 
            { 
                link[i] = t; 
                return 1; 
            } 
        } 
    } 
    return 0; 
} 
 
int main() 
{ 
    //freopen("f://data.in", "r", stdin); 
    int T; 
    scanf("%d", &T); 
    while(T --) 
    { 
        memset(map, 0, sizeof(map)); 
        cat_num = dog_num = 0; 
        scanf("%d %d %d", &c, &d, &v); 
        for(int i = 0; i < v; ++ i) 
        { 
            char a[10], b[10]; 
            scanf("%s %s", a, b); 
            if(a[0] == 'C') 
            {   www.2cto.com
                strcmp(cat[cat_num].str1, a); 
                strcmp(cat[cat_num].str2, b); 
                cat_num ++; 
            } 
            else 
            { 
                strcmp(dog[dog_num].str1, a); 
                strcmp(dog[dog_num].str2, b); 
                dog_num ++; 
            } 
        } 
        for(int i = 0; i < cat_num; ++ i) 
            for(int j = 0; j < dog_num; ++ j) 
                if(!strcmp(cat[i].str1, dog[j].str2) || !strcmp(cat[i].str2, dog[j].str1)) 
                    map[i][j] = 1; 
        int ans = 0; 
        memset(link, -1, sizeof(link)); 
        for(int i = 0; i < cat_num; ++ i) 
        { 
            memset(useif, 0, sizeof(useif)); 
            if(can(i)) ans++; 
        } 
        printf("%d\n",v - ans);     } 
    return 0; 
} 
作者：lhshaoren