hdu1068-二分图最大独立集

超、凢脫俗 2022-07-12 05:02 141阅读 0赞

# Girls and Boys #

**Time Limit: 20000/10000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)  
Total Submission(s): 11114    Accepted Submission(s): 5201**

Problem Description

the second year of the university somebody started a study on the romantic relations between the students. The relation “romantically involved” is defined between one girl and one boy. For the study reasons it is necessary to find out the maximum set satisfying the condition: there are no two students in the set who have been “romantically involved”. The result of the program is the number of students in such a set.  
  
The input contains several data sets in text format. Each data set represents one set of subjects of the study, with the following description:  
  
the number of students  
the description of each student, in the following format  
student\_identifier:(number\_of\_romantic\_relations) student\_identifier1 student\_identifier2 student\_identifier3 ...  
or  
student\_identifier:(0)  
  
The student\_identifier is an integer number between 0 and n-1, for n subjects.  
For each given data set, the program should write to standard output a line containing the result.

Sample Input

7
    0: (3) 4 5 6
    1: (2) 4 6
    2: (0)
    3: (0)
    4: (2) 0 1
    5: (1) 0
    6: (2) 0 1
    3
    0: (2) 1 2
    1: (1) 0
    2: (1) 0

Sample Output

5
    2

Source

[Southeastern Europe 2000][]

题目大意：

给你n个人编号为0 - n-1，他们有些人相互之间存在一种关系见题目描述，现在告诉你这些关系，但是有些给出的是x和y但没有说y和x，所以我们可以补全这里或者只要满足一个就行，如果补全就是无向图，然后求最多有多少个人他们之间没有两个人是存在这种关系的！

题目思路：

这是最大独立集的裸题，而我们知道最大独立集= 定点数-最大匹配，而如果是无向图最大匹配就要除以2，所以我们只需跑一边最大匹配就行！

AC代码:

#include<cstring>
    #include<cstdio>
    
    const int maxn = 1e3+10;
    
    bool vis[maxn],mp[maxn][maxn];
    int link[maxn];
    
    int n;
    
    bool dfs(int u){
        for(int i=1;i<=n;i++){
            if(!vis[i]&&mp[u][i]){
                vis[i]=true;
                if(link[i]==-1||dfs(link[i])){
                    link[i]=u;
                    return true;
                }
            }
        }
        return false;
    }
    
    int main()
    {
        while(~scanf("%d",&n)){
            memset(link,-1,sizeof(link));
            memset(mp,false,sizeof(mp));
            for(int i=1;i<=n;i++){
                int id,num=0,j=1;
                char str[20];
                scanf("%d: %s",&id,str);id++;
                int len = strlen(str);
                while(j<len-1){
                    num=num*10+str[j]-'0';j++;
                }
                while(num--){
                    int v;scanf("%d",&v);v++;
                    mp[id][v]=mp[v][id]=true;
                }
            }
            int ans = 0;
            for(int i=1;i<=n;i++){
                memset(vis,false,sizeof(vis));
                if(dfs(i))ans++;
            }
            printf("%d\n",n-ans/2);
        }
        return 0;
    }

[Southeastern Europe 2000]: http://acm.hdu.edu.cn/search.php?field=problem&key=Southeastern+Europe+2000&source=1&searchmode=source