P6680 [CCO 2019] Marshmallow Molecules

思路

一个简单的观察是以 \(a\) 从小到大的顺序操作能将所有可加的边都加上，因为操作 \(a = i\) 时不会使小于 \(i\) 的点增加新边，进而产生新的 \(a < i\) 操作。则有一个暴力的思路是从 \(1\) 到 \(n\) 枚举 \(a\)，将所有 \(a\) 连向大于 \(a\) 的点之间都加上边，复杂度 \(O(n^3)\)。

显然两两暴力连接是没前途的。观察操作形式，发现枚举 \(a\) 时只要找到 \(a\) 连向的点中最小的 \(x\)，并只添 \(x\) 与其他 \(a\) 连向的点的边，得到的结果与暴力相同，因为除 \(x\) 外的点之间未连接的边会在 \(a = x\) 时进一步连接，直至最终全部被添加。

此时操作相当于将 \(a\) 与 \(x\) 向编号大的点连出的点集合并，并计算 \(x\) 点集中新增的点数。使用启发式合并，可以做到 \(O(M \log M)\)。

Code

#include<iostream>
#include<set>
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
const int N=1e5+5;
int n,m;
long long ans=0;
set<int>G[N];
int main()
{//freopen("verify.in","r",stdin);//freopen("verify.out","w",stdout);IOS;cin>>n>>m;for(int i=1;i<=m;i++){int u,v;cin>>u>>v;G[u].insert(v);}for(int i=1;i<=n;i++){ans+=G[i].size();if(!G[i].empty()){int maxx=*G[i].begin();G[i].erase(maxx);if(G[i].size()>G[maxx].size())swap(G[i],G[maxx]);for(int v:G[i])G[maxx].insert(v);}}cout<<ans<<'\n';return 0;
}

完结撒花～