題意：

有n個人，其中有m組，兩兩互斥，現(xiàn)在要分成兩個班，但最終求的確是最多有多少對不互斥的。

題目：

鏈接：https://ac.nowcoder.com/acm/contest/16741/F
來源：?？途W(wǎng)
The big day has fifinally arrived: today you are going to form groups of two in which you will do the end-of-the-year project. When you arrive at school, you learn that the teacher of the other class is sick, and that your teacher, Mr. B.A.P. Cee, will also have to make groups for the other class. Mr. B.A.P. Cee is a smart guy and realizes that he can use these unfortunate circumstances to his advantage.

Ending up with groups of one should be avoided at all cost, so mixing the students of the two classes may avoid this situation. However, while it is easy to pair up two students from the same class, it is more diffiffifficult to match up students from difffferen classes. Throughout the years there has been a lot of rivalry between the two groups, and many students dislike students in the other class. Mr. B.A.P. Cee knows which pairs of students will result in a fifight and a failed project.

You are given a list of pairs of students who cannot work together. How many disjoint groups of two can Mr. B.A.P. Cee make that will not result in a failed project?

輸入描述:

The input consists of:
? A line with two integers n (1 ≤ n ≤ 105), the number of students, and m (0 ≤ m ≤ 2 · 105), the number of pairs of students who cannot work together.
? m lines, each with two distinct integers i and j (1 ≤ i, j ≤ n, i = j), giving a pair of students who cannot work together.
Students are identifified by the numbers 1 through n. It is guaranteed that it is possible to split the students into two classes in such a way that all students from the same class get along.

輸出描述:

Output the number of pairs of students Mr. B.A.P. Cee can make without making any pair of students who cannot work together.

示例1

輸入

3 2
1 2
3 1

輸出

1

示例2

輸入

5 6
1 4
2 4
3 4
1 5
2 5
3 5

輸出

2

示例3

輸入

6 6
1 4
2 5
3 6
1 5
3 5
2 6

輸出

3

分析：

1.因為這道題求的是兩個不互斥的對數(shù)，最大能有多少對不互斥的。所以我們只需要保證區(qū)分后，兩個班里面不存在不互斥的就可以了。
2.這里我直接用vector數(shù)組處理，兩兩互斥的狀況，建圖，即相鄰互斥，隔代在同一個班即可
3. 分完班之后，按理來說，直接每個班成對即可，即su/2+sm/2；但當兩個并不是都互斥時，兩個班里只要存在一對不互斥時，此時這兩個就可以成為一對不互斥，此時的對數(shù)就是n/2，判斷條件即為su*sm==m
4. 前面說了題意并不需要可以用唯一方法分出兩個班，還有一種是用并查集擴展域，用并查集及擴展域存儲同類關系和異類關系；也貼在下面

AC代碼：

#include<stdio.h> #include<string.h> #include<math.h> #include<algorithm> #include<vector> #include<iostream> using namespace std; typedef long long ll; const int M=2e5+10; int n,m,a,b; vector<int>ve[M]; int vis[M]; void dfs(int u,int pre,int color){vis[pre]=color;for(int i=0;i<ve[pre].size();i++){int k=ve[pre][i];if(u==k||vis[k]!=-1) continue;dfs(pre,k,color^1);} } int main(){cin>>n>>m;for(int i=1;i<=n;i++)vis[i]=-1;for(int i=0;i<m;i++){cin>>a>>b;ve[a].push_back(b);ve[b].push_back(a);}int su=0,sm=0;for(int i=1;i<=n;i++){if(vis[i]==-1){dfs(0,i,0);}if(vis[i]==0) ++su;else ++sm;}if(su*sm==m) printf("%d\n",su/2+sm/2);else printf("%d\n",n/2);return 0; } /**有一種情況需要特判： 如果兩班均是奇數(shù)個人，且有一班中某人的敵人數(shù)小于另一班人數(shù)，則說明此人可以與另一班某同學組組；*/ #include <bits/stdc++.h> using namespace std; typedef long long ll; vector<int> vec,tn[100005];//vec存一班的同學編號，tn[i]存儲i號同學的敵人 int fa[200005];//擴展域并查集 int find(int x)//此題中，find(x)的返回值為1或0 {if(fa[x]!=x)return fa[x]=find(fa[x]);return x; } int main() {int n,m;int a,b;cin>>n>>m;for(int i=1;i<=n;i++)fa[i]=1;for(int i=1;i<=m;i++){scanf("%d%d",&a,&b);if(a>b)swap(a,b);tn[a].push_back(b);tn[b].push_back(a);fa[b]=a+n;fa[b+n]=a;}int s,l;s=l=0;//l與s存儲兩班人數(shù)for(int i=1;i<=n;i++){if(find(i))l++;else s++,vec.push_back(i);}if(s&1&&l&1){for(int i=0;i<vec.size();i++)if(tn[vec[i]].size()!=l){s--,l++;break;}}printf("%d",s/2+l/2);return 0; }

總結

以上是生活随笔為你收集整理的2021年度训练联盟热身训练赛第五场F题Group Project的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。