題目鏈接：點擊查看

題目大意：給出n只狗和m只貓，現在有p個小朋友，每個小朋友都有一只喜歡的貓和一只不喜歡的狗，或者有一只喜歡的狗和一只不喜歡的貓，如果一個小朋友喜歡的動物還在，不喜歡的動物走了，那么這個小朋友是開心的，現在怎么樣讓小動物走，才能讓開心的小朋友最多

題目分析：其實題目中的貓和狗都是沒有的無效信息，意在讓我們按照貓和狗劃分二分圖，其實不然，有多少種動物都沒有關系，實際上只是和每個小朋友喜歡以及不喜歡的動物有關系

因為這個題目中，留下一個動物或趕走一個動物，會造成的影響是對于小朋友而言的，所以我們要對于小朋友劃分二分圖，具體怎么劃分呢，因為題目明確說明了要求出開心的小朋友的最大集合，那么在這個集合中的小朋友必須滿足的條件就是任意一個小朋友喜歡的動物和其他所有小朋友不喜歡的動物不能相同，同理任意一個小朋友不喜歡的動物也不能和其他小朋友喜歡的動物相同，這樣一來只需要將集合中所有小朋友不喜歡的動物趕走就能讓這些小朋友開心了

說到這里，這不就是要求集合中的所有點都互相獨立，換句話說不就是要求最大獨立集，所以我們讓所有有矛盾的小朋友互相建邊，用匈牙利跑一下最大獨立集就是這個題目的答案了，因為我們建立的是無向邊，所以最后匹配后的答案記得除以二

代碼：

#include<iostream> #include<cstdlib> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<queue> #include<list> #include<vector> #include<set> #include<map> #include<sstream> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=510;struct Node {string like,dislike; }a[N];int match[N],vis[N],vis_cnt,n,m,p;bool maze[N][N];bool dfs(int x) {for(int i=1;i<=p;i++){if(vis[i]!=vis_cnt&&maze[x][i]){vis[i]=vis_cnt;if(!match[i]||dfs(match[i])){match[i]=x;return true;}} }return false; }void init() {vis_cnt=0;memset(maze,false,sizeof(maze));memset(vis,-1,sizeof(vis));memset(match,0,sizeof(match)); }int main() { // freopen("input.txt","r",stdin); // ios::sync_with_stdio(false);while(scanf("%d%d%d",&n,&m,&p)!=EOF){init();for(int i=1;i<=p;i++)cin>>a[i].like>>a[i].dislike;for(int i=1;i<=p;i++)for(int j=1;j<=p;j++)if(a[i].like==a[j].dislike||a[i].dislike==a[j].like)maze[i][j]=true;int ans=0;for(int i=1;i<=p;i++,vis_cnt++)if(dfs(i))ans++;printf("%d\n",p-ans/2);}return 0; }

?

總結

以上是生活随笔為你收集整理的HDU - 3829 Cat VS Dog(最大独立集-二分图最大匹配)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。