hdu1068-二分图最大独立集

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


题目大意:

                 给你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;
}





全部评论

相关推荐

06-25 09:33
厦门大学 Java
程序员饺子:现在日常估计没啥hc了,等到八月多估计就慢慢有了。双九✌🏻不用焦虑的
投递快手等公司8个岗位
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务