【BZOJ4264】小C找朋友解题笔记

鸽子爱咕咕 · 2022-11-16 22:09:27 · 个人记录

Description

幼儿园里有N个小C，两个小C之间可能是朋友也可能不是。所有小C之间的朋友关系构成了一个无向图，这个无向图中有M条边。

园长ATM发现对于两个（不同的）小C_i和小C_j，如果其他的所有小C要么同时是i,j的朋友，要么同时不是i,j朋友的话，这两个小C就很有可能一起去吃饭，成为一对好J友。出于一些未知的原因，ATM需要你帮他求出可能成为好J友的小C的对数。

Input

第一行一个数N,M，如题目描述。接下来M行，每行2个数表示一条无向边。

Output

输出可能成为好J友的小C的对数。

AC代码：

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <map>
#define int long long
using namespace std;
const int N=(int)1e6+10;

int n,m,ans;
int a[N],val[N];
map<int,int>mm;

inline int read(){
    int x=0;
    char c=getchar();
    while(c<'0' || c>'9') c=getchar();
    while(c>='0' && c<='9'){x=(x<<3)+(x<<1)+(c^48);c=getchar();}
    return x;
}

signed main(){
    srand(time(0));
    n=read(),m=read();
    for(int i=1;i<=n;++i) val[i]=(rand()*rand()%(int)1e18*rand())+i;
    for(int i=1;i<=m;++i){
        int u=read(),v=read();
        a[u]^=val[v],a[v]^=val[u];
    }
    for(int i=1;i<=n;++i){
        ans+=mm[a[i]];
        ++mm[a[i]];
    } mm.clear();
    for(int i=1;i<=n;++i) a[i]^=val[i];
    for(int i=1;i<=n;++i){
        ans+=mm[a[i]];
        ++mm[a[i]];
    } cout<<ans;
    return 0;
}

构造一些小哈希，挺妙的。

由“对于两个（不同的）小C_i和小C_j，如果其他的所有小C要么同时是i,j的朋友，要么同时不是i,j朋友的话，这两个小C就很有可能成为一对好友”可知：

·若i与j不是朋友，当i与j连的结点完全相同时，i与j就是一对好J友。

·若i与j是朋友，那么当除去i与j的连边，其它连的结点完全相同时，i与j也是一对好J友。

我们可以采用如下方式判断两个点所连的所有结点是否完全相同：

1.先给每个点赋一个随机权值val[]。

2.若u与v有连边，则将a[u]与val[v]进行异或。

3.以上过程完成后，若a[u] = a[v]，则(u,v)是一对好J友。

值得注意的是：可能有多个点的a[]值相等。若有k个点的值相等，那么这个值所贡献的答案就是1+2+...+(k-1)=(k-1)(k-2)/k.

还有两个小细节：

1.在赋随机权值时，若令val[i]=rand() \times rand() \times rand()，则val[]一定是除1与本身之外至少具有3个因子的合数。此时哈希冲突的概率较大。若将val[i]加上i，则两个不同的val[i]具有相同因数的概率将大大降低，亲测极其有效。

2.如何判断i与j本来就是朋友时，他们是不是好J友的情况？只需要让i= i xor val[i]即可。此举相当与给i与j都加上了一条连向自己的边。因此需要对上述不同的两种情况（i与j是或不是朋友）分别累加答案。

【BZOJ4264】小C找朋友 解题笔记

【BZOJ4264】小C找朋友解题笔记