Dream Team

Summer training is coming soon, and in order to achieve good results in the upcoming contests, everyone wants to find their favorite teammates to form their own dream team!

There are $3n$ students in the training team with corresponding numbers $1$ to $3n$ , and they will form $n$ teams, each consisting of $3$ students . It is now known that there are $m$ pairs of students $(x_i, y_i)$ who are directly familiar with each other (i.e. $x_i$ is directly familiar with $y_i$ , and $y_i$ is directly familiar with $x_i$ ) .

Friends of friends are friends. We define that student $a$ is familiar with student $b$ if one of the following conditions is met:

1. $a$ is directly familiar with $b$ , or
2. There exists a series of students $x_1,x_2,\dots, x_k\ (k > 0)$ satisfies:

$a$ is directly familiar with $x_1$
For all $1\le i< k$ , $x_i$ is directly familiar with $x_{i+1}$
$x_k$ is directly familiar with $b$

As a retired contestant, Colin clearly knows that it is important for teammates to be familiar with each other. We define a student's anxiety level as the number of students in his team that he is not familiar with (of course everyone is familiar with himself) . Now Colin wants you to find a plan satisfies: divide all $3n$ students into $n$ teams, and each student is in exactly one team, and each team has exactly $3$ students, and minimize the sum of anxiety level of all $3n$ students.

You only need to tell Colin the minimum sum of anxiety level of all $3n$ students.

The first line contains two integers $n, m\text{ }(1\le n\le 10^6,1\le m\le 2\times 10^5)$ , representing there are $3n$ students and $m$ pairs of students directly familiar with each other.

For the following $m$ lines, each line contains two integers $x_i, y_i\ (1 \le x_i,y_i \le 3\times n, x_i \ne y_i)$ , representing $x_i, y_i$ are directly familiar with each other.

#include <iostream> using namespace std; int n,m,x,y,a,b,f[3000006],num[3000006]; int fnd(int x){ return f[x]==x?x:f[x]=fnd(f[x]); } int main() { cin>>n>>m; n*=3; for(int i=1;i<=n;i++) f[i]=i; for(int i=1;i<=m;i++){ cin>>x>>y; int fx=fnd(x),fy=fnd(y); if(fx!=fy) f[fx]=fy; } for(int i=1;i<=n;i++) num[fnd(i)]++; for(int i=1;i<=n;i++){ if(f[i]==i){ if(num[i]%3==2) a++; else if(num[i]%3==1) b++; } } if(a>=b) cout<<b*4+(a-b)/3*8; else cout<<(a+b)*2; return 0; }

#include <iostream> using namespace std; int n,m,x,y,a,b,f[3000001],d[3000001],i; int fnd(int a){ return f[a]==a?a:f[a]=fnd(f[a]); } int main() { cin>>n>>m; n*=3; for(;i<n;i++) f[i]=i,d[i]=1; for(i=0;i<m;i++){ scanf("%d%d",&x,&y); x=fnd(x),y=fnd(y); if(x!=y) f[x]=y,d[y]+=d[x]; } for(i=0;i<n;i++){ if(f[i]==i){ if(d[i]%3==2) a++; if(d[i]%3==1) b++; } } cout<<(a>b?b*4+(a-b)/3*8:(a+b)*2); return 0; }

详情