程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HDU 1068 Girls and Boys(最大獨立集)

HDU 1068 Girls and Boys(最大獨立集)

編輯:C++入門知識

[cpp] 
/*
題意:n個同學,一些男女同學會有緣分成為情侶,格式ni:(m) n1 n2 n3表示同學ni有緣與n1,n2,n3成為情侶,求集合中不存在有緣成為情侶的同學的最大同學數。
題解:
獨立集:圖的頂點集的子集,其中任意兩點不相鄰
最大獨立集 = 頂點數 - 最大匹配數
由於本題是從整個點集搜索,並不是將點集分開成(A)(B),(1->2)(2->1)對稱存在,所以相當於搜索了兩遍。因此真正最大匹配數等於最大匹配數/2.
具體我也不明白其中的原理,只是理解。
*/ 
 
#include <iostream> 
using namespace std; 
 
const int nMax = 500; 
int n; 
int map[nMax][nMax]; 
int link[nMax]; 
int useif[nMax]; 
 
bool can(int t) 

    for(int i = 0; i < n; ++ 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); 
    while(scanf("%d", &n) != EOF) 
    { 
        memset(map, 0, sizeof(map)); 
        memset(link, -1, sizeof(link)); 
        int u, k, v; 
        for(int i = 0; i < n; ++ i) 
        { 
            scanf("%d: (%d)", &u, &k); 
            while(k --) 
            { 
                scanf("%d", &v); 
                map[u][v] = 1; 
            }  www.2cto.com
        } 
        int num = 0; 
        for(int i = 0; i < n; ++ i) 
        { 
            memset(useif, 0, sizeof(useif)); 
            if(can(i)) ++ num; 
        } 
        printf("%d\n", n - num / 2); 
    } 
    return 0; 

作者:lhshaoren

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved