题目描述

Professor Alex will organize students to attend an academic conference.

Alex has n excellent students, and he decides to select some of them (possibly none) to attend the conference. They form a group. Some pairs of them are friends.

The friendly value of the group is initially 0. For each couple of friends (x,y), if both of them attend the conference, the friendly value of the group will increase 1, and if only one of them attends the conference, the friendly value of the group will decrease 1. If k students attend the conference, the friendly value of the group will decrease k.

Alex wants to make the group more friendly. Please output the maximum friendly value of the group.

题意：

有m对好朋友，n个人
如果好朋友同时出现宴会，好感值+1，宴会上如果一共有x个人，好感值-x，问好感值最大是多少？

题解：

并查集做法
我们设两个数组

int sum[maxn];//人数 
int pairr[maxn];//朋友对数

分别存的是人数和朋友的对数
可以理解成人数为扣分项，朋友的对数为加分项
我们都知道并查集在路径压缩后，一个连通块内的元素都会指向一个元素，那我们就把这个连通块内所有人数，以及朋友的对数全部加到这个元素上，最后统计时也方便统计
注意：初始化时，人数初始化为0，因为自己本身也是人。。emmm。。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=3e5+9;
int fa[maxn];
int sum[maxn];//人数 
int pairr[maxn];//朋友对数 
int find(int x)
{
    if(fa[x]==x)return x;
    else return fa[x]=find(fa[x]);
}
void unionn(int x,int y)
{

    x=find(x);
    y=find(y);
    pairr[x]++;
    if(x==y)return;
    fa[y]=x;//构建新的父子关系 
    pairr[x]+=pairr[y];
    sum[x]+=sum[y];
}
void init(int n)
{
    for(int i=1;i<=n;i++)
    {
        fa[i]=i;
        sum[i]=1; 
    }
    //memset(sum,0,sizeof sum);
    memset(pairr,0,sizeof pairr);
}
int main()
{
    ios::sync_with_stdio(false);
    int t;
    cin>>t;
    for(int ii=1;ii<=t;ii++)
    {

        int tot=0;
        int n,m;
        cin>>n>>m;
        init(n);
        for(int i=1;i<=m;i++)
        {
            int x,y;
            cin>>x>>y;
            unionn(x,y);
        }
        long long summ=0;
        for(int i=1;i<=n;i++)
        {
            if(fa[i]==i)
            {
                summ+=max(0,pairr[i]-sum[i]);
            }
        }
        printf("Case #%d: %lld\n", ii, summ);
    } 
}