企业官网建设流程全解析

P10163 [DTCPC 2024] 平方树

题目描述

给你一个森林，每条边有一个方向。

你可以进行两种操作：

• 新增一个点。

• 将两个点之间连一条有向边。

你要使得最后将所有有向边看成无向边后，图形成一棵树，且每个点的出度都是平方数。

给出一种新增点数最少的方案。

输入格式

第一行两个整数n,mn,mn,m（1≤m<n≤1051\le m \lt n \le 10^51≤m<n≤105）表示这个森林的点数和边数。

接下来mmm行，每行两个数u,vu,vu,v（1≤u,v≤n1\le u,v\le n1≤u,v≤n）表示一条uuu连向vvv的有向边。

保证将每条边看作无向边后，这张图是森林。

输出格式

第一行两个整数x,yx,yx,y表示你的新增点数和连边数。

接下来yyy行，每行两个数u,vu,vu,v表示新增一条uuu连向vvv的有向边，你要保证1≤u,v≤n+x1\le u,v\le n+x1≤u,v≤n+x。

输入输出样例 #1

输入 #1

3 2 1 2 1 3

输出 #1

2 2 1 4 1 5

思路

直接写即可。

代码

#include<bits/stdc++.h>usingnamespacestd;longlongn,m,uu,vv2,fa[1000006],u[1000006],oi[1005],uo[1000006],ok[1000006],oc=0,ov=0,hu[1000006],ku[1000006],ih=0,op=0,ik=0;vector<longlong>v[100005],vv[100005];structone{longlongx,y;}a[1000006];longlongfind(longlonga1){if(a1==fa[a1]){returna1;}else{fa[a1]=find(fa[a1]);returnfa[a1];}}longlongcn2(longlonga1){longlongl=0,r=1000,md=1001;while(l<=r){longlongmid=(l+r)/2;if(oi[mid]>=a1){md=min(md,mid);r=mid-1;}else{l=mid+1;}}returnoi[md]-a1;}intmain(){cin>>n>>m;for(inti=1;i<=1000000;i++){fa[i]=i;}for(inti=0;i<=1001;i++){oi[i]=i*i;}for(inti=1;i<=m;i++){cin>>uu>>vv2;v[uu].push_back(vv2);u[uu]++;if(find(uu)!=find(vv2)){fa[find(vv2)]=find(uu);}vv[uu].push_back(vv2);vv[vv2].push_back(uu);}for(inti=1;i<=n;i++){uo[i]=cn2(u[i]);// cout<<i<<" "<<u[i]<<" "<<uo[i]<<endl;ov+=uo[i];if(uo[i]!=0){ku[++ik]=i;}}for(inti=1;i<=n;i++){if(fa[i]==i){ok[++oc]=i;}}if(oc<=ov){while(oc>=2){longlonga1=find(ok[oc]),b1=find(ok[oc-1]),c1=ku[ik];if(uo[c1]==0){ik--;c1=ku[ik-1];}if(find(c1)!=a1){a[++ih]=(one){c1,a1};fa[a1]=find(c1);uo[c1]--;oc--;}else{a[++ih]=(one){c1,b1};fa[b1]=find(c1);uo[c1]--;oc--;ok[oc]=ok[oc+1];}}for(inti=1;i<=ik;i++){for(intj=1;j<=uo[ku[i]];j++){a[++ih]=(one){ku[i],n+(++op)};}}cout<<op<<" "<<ih<<endl;for(inti=1;i<=ih;i++){cout<<a[i].x<<" "<<a[i].y<<endl;}}else{ov=0;ik=0;for(inti=1;i<=n;i++){uo[i]=cn2(u[i]);// cout<<i<<" "<<u[i]<<" "<<uo[i]<<endl;if(u[i]==0){ku[++ik]=i;}}for(inti=1;i<=n;i++){uo[i]=cn2(u[i]);// cout<<i<<" "<<u[i]<<" "<<uo[i]<<endl;ov+=uo[i];if(uo[i]!=0){ku[++ik]=i;}if(u[i]==0){uo[i]=1;}}while(oc>=2){longlonga1=find(ok[oc]),b1=find(ok[oc-1]),c1=ku[ik];if(uo[c1]==0){ik--;c1=ku[ik-1];}if(find(c1)!=a1){a[++ih]=(one){c1,a1};fa[a1]=find(c1);uo[c1]--;oc--;}else{a[++ih]=(one){c1,b1};fa[b1]=find(c1);uo[c1]--;oc--;ok[oc]=ok[oc+1];}}cout<<op<<" "<<ih<<endl;for(inti=1;i<=ih;i++){cout<<a[i].x<<" "<<a[i].y<<endl;}}return0;}