首页 > 代码库 > HDU 3829 - Cat VS Dog （二分图最大独立集）

HDU 3829 - Cat VS Dog （二分图最大独立集）

2024-07-02 07:08:43   225人阅读

题意：动物园有n只猫和m条狗，现在有p个小孩，他们有的喜欢猫，有的喜欢狗，其中喜欢猫的一定不喜欢狗，喜欢狗的一定不喜欢猫。现在管理员要从动物园中移除一些动物，如果一个小孩喜欢的动物留了下来而不喜欢的动物被移走，这个小孩会很高兴。现在问最多可以让多少个小孩高兴。

 

此题是求二分图最大独立集。

二分图比较明显，但是难在建图。这个题是找到最多的喜欢猫和喜欢狗而不互相冲突的小孩，这样我们将喜欢动物相互冲突的小孩之间连边，问题就变成了求二分图的最大独立集。

在二分图中，最大独立集=顶点数-最大匹配数。

求解二分图最大匹配可以用匈牙利算法。

 

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cmath>
 4 #include<algorithm>
 5 #include<cstdlib>
 6 #include<cstdio>
 7 #include<vector>
 8 using namespace std;
 9 vector< pair<string,string> > vec1,vec2;
10 bool gl[505][505];
11 bool vis[505];
12 int link[505];
13 bool match(int x)
14 {
15     for(int i=0;i<vec2.size();++i)
16     {
17         if(gl[x][i]&&!vis[i])
18         {
19             vis[i]=true;
20             if(link[i]==-1||match(link[i]))
21             {
22                 link[i]=x;
23                 return true;
24             }
25         }
26     }
27     return false;
28 }
29 int main()
30 {
31     int n,m,p;
32     while(cin>>n>>m>>p)
33     {
34         string a,b;
35         vec1.clear();
36         vec2.clear();
37         for(int i=0; i<p; ++i)
38         {
39             cin>>a>>b;
40             if(a[0]==‘C‘)
41                 vec1.push_back(pair<string,string>(a,b));
42             else
43                 vec2.push_back(pair<string,string>(a,b));
44         }
45         memset(gl,0,sizeof(gl));
46         for(int i=0; i<vec1.size(); ++i)
47         {
48             for(int j=0; j<vec2.size(); ++j)
49                 if(vec1[i].first==vec2[j].second||vec1[i].second==vec2[j].first)
50                     gl[i][j]=true;
51         }
52         int res=0;
53         memset(link,-1,sizeof(link));
54         for(int i=0;i<vec1.size();++i)
55         {
56             memset(vis,0,sizeof(vis));
57             if(match(i)) res++;
58         }
59         cout<<p-res<<endl;
60     }
61     return 0;
62 }
View Code

 

 

 


联系
我们