poj 1466

Girls and Boys

题意：有人想对学校里面的男女学生做暧昧关系做研究，要将没有暧昧关系的学生分到同一个组里面，问一个组最大人数是多少。

分析：每两个节点之间都不相邻，也就是求二分图最大点独立数。在没有孤立点的二分图里，最大点独立数＝n-最大匹配数。

View Code

 1 #include<cstdio>
 2 #include<vector>
 3 using namespace std;
 4 vector<int> vex[500],group;
 5 int n,m,max_match,sum,mat[500],set[500],counter;
 6 bool visited[500],over[500];
 7 int path(int u)
 8 {
 9     int i,v;
10     for(i=0;i<vex[u].size();i++)
11     {
12         v=vex[u][i];
13         if(!visited[v])
14         {
15             visited[v]=true;
16             if(mat[v]==-1 || path(mat[v]))
17             {
18                 mat[v]=u;
19                 mat[u]=v;
20                 return 1;
21             }
22         }
23     }
24     return 0;
25 }
26 int Hungary()
27 {
28     int ans=0,i,j;
29     for(i=0;i<n;i++)
30         mat[i]=-1;
31     for(i=0;i<group.size();i++)
32     {
33         for(j=0;j<n;j++)
34             visited[j]=false;
35         ans+=path(group[i]);
36     }
37     return ans;
38 }
39 void dfs(int u,int color)
40 {
41     int i,v;
42     over[u]=true;
43     counter++;
44     if(color==0)
45         group.push_back(u);
46     for(i=0;i<vex[u].size();i++)
47     {
48         v=vex[u][i];
49         if(!over[v])
50             dfs(v,(color+1)%2);
51     }
52 }
53 int main()
54 {
55     int i,j,e;
56     while(~scanf("%d",&n))
57     {
58         for(i=0;i<n;i++)
59         {
60             scanf("%d: (%d)",&i,&m);
61             for(j=0;j<m;j++)
62             {
63                 scanf("%d",&e);
64                 vex[i].push_back(e);
65                 vex[e].push_back(i);
66             }
67             over[i]=false;
68         }
69         sum=0;
70         for(i=0;i<n;i++)
71         {
72             if(!over[i])
73             {
74                 counter=0;
75                 dfs(i,0);
76                 max_match=Hungary();
77                 sum+=counter-max_match;
78                 group.clear();
79             }
80         }
81         printf("%d\n",sum);
82         for(i=0;i<n;i++)
83             vex[i].clear();
84     }
85     return 0;
86 }