题解：树论-拓冰建站

时间限制空间限制输入文件名输出文件名

\(\text{1000ms}\) \(\text{512MB}\) tree.in tree.out

时间限制	空间限制	输入文件名	输出文件名
\(\text{1000ms}\)	\(\text{512MB}\)	`tree.in`	`tree.out`

题目

题目描述

给定一张大小为 \(n\) 的完全图，点的编号为 \(1\sim n\)，点 \(i\) 与点 \(j\) 之间有一条权值为 \(\dfrac{f(i,j)+f(j,i)}2\) 的无向边，其中：

\[f(i,j)= \left\{ \begin{aligned} \begin{aligned} &\dfrac{i\cdot f(j,i\bmod j)}{i\bmod j}\\ &\dfrac ij \end{aligned} \begin{aligned} &i\bmod j\ne0\\\\ &i\bmod j=0\\ \end{aligned} \end{aligned} \right. \]

求这张图的最小生成树。

最小生成树：满足边权和最小的包含 \(n\) 个点 \(n-1\) 条边的连通子图。

输入格式

一行一个正整数 \(n\)，表示图的大小。

输出格式

第一行输出一个实数，表示这张图的最小生成树的边权和，四舍五入到整数。

之后 \(n-1\) 行，每行输出两个以空格隔开的正整数 \(u,v\)，表示最小生成树的一条边。

输入输出样例

输入 #1

输出 #1

说明/提示

数据范围

测试点编号	\(n\leq\)
\(1\sim2\)	\(10\)
\(3\sim5\)	\(300\)
\(6\sim7\)	\(5000\)
\(8\sim9\)	\(100000\)
\(10\)	\(3000000\)

对于所有数据，满足 \(2\leq n\leq3\times10^6\)。

若你只答对了最小生成树的边权和，则你可以得到 \(40\%\) 的分数。注意，即使你不知道最小生成树的形态，你也需要输出任意一棵树，否则会出现不可预知的错误。

附件

tree.zip

题解

\(70\text{pts}\)

直接按题意模拟，求最小生成树即可。

但考虑到 Kruskal 算法在完全图上劣于 Prim 算法，因此使用 Prim 算法 \(\mathcal O\left(n^2\right)\) 求解。

参考代码：

//#include<bits/stdc++.h>
#include<algorithm> 
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<ctime>
#include<deque>
#include<queue>
#include<stack>
#include<list>
using namespace std;
inline char gc(){static int p1,p2;static char buf[1<<20];if(p1==p2)p1=0,p2=fread(buf,1,1<<20,stdin);if(p1==p2)return EOF;return buf[p1++];
}
template<typename T>
inline void Read(T &x){x=0;char ch=gc();for(;ch<'0'||'9'<ch;ch=gc());for(;'0'<=ch&&ch<='9';ch=gc())x=(x<<3)+(x<<1)+(ch^48);
}
#define putchar putchar_unlocked 
template<typename T>
inline void Write(T x){static char s[101];int top=0;do{s[++top]=x%10+'0';x/=10;}while(x);while(top)putchar(s[top--]);
}
const int N=3e6;
typedef long long ll;
int n,father[N+1];
double f(int i,int j){int pl=i%j;if(pl)return i*f(j,pl)/pl;else return 1.0*i/j;
} 
ll Prim(int s){static bool vis[N+1];static double dis[N+1];fill(dis+1,dis+n+1,2147483647);dis[s]=0;double ans=0;while(true){int Min=2147483647,u=-1;for(int i=1;i<=n;i++){if(!vis[i]&&dis[i]<Min)Min=dis[i],u=i;}if(u==-1)break;vis[u]=true;ans+=dis[u];for(int i=1;i<=n;i++){if(!vis[i]&&(f(u,i)+f(i,u))/2<dis[i]){dis[i]=(f(u,i)+f(i,u))/2;father[i]=u;}} }return round(ans);//四舍五入
}
int main(){freopen("tree.in","r",stdin);freopen("tree.out","w",stdout);Read(n);Write(Prim(1));putchar(10);for(int i=1;i<=n;i++){if(father[i]){Write(father[i]);putchar(32);Write(i);putchar(10);}}fclose(stdin);fclose(stdout);return 0;
}

\(90\text{pts}\)

这个方法其实对正解有些启发玄学。

先看代码：

//#include<bits/stdc++.h>
#include<algorithm> 
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<ctime>
#include<deque>
#include<queue>
#include<stack>
#include<list>
using namespace std;
inline char gc(){static int p1,p2;static char buf[1<<20];if(p1==p2)p1=0,p2=fread(buf,1,1<<20,stdin);if(p1==p2)return EOF;return buf[p1++];
}
template<typename T>
inline void Read(T &x){x=0;char ch=gc();for(;ch<'0'||'9'<ch;ch=gc());for(;'0'<=ch&&ch<='9';ch=gc())x=(x<<3)+(x<<1)+(ch^48);
}
#define putchar putchar_unlocked
template<typename T>
inline void Write(T x){static char s[101];int top=0;do{s[++top]=x%10+'0';x/=10;}while(x);while(top)putchar(s[top--]);
}
const int N=3e6;
typedef long long ll;
typedef pair<double,int> pr;
int n,father[N+1];
ll Prim(int s){static bool vis[N+1];static double dis[N+1];priority_queue<pr,vector<pr>,greater<pr> >q; fill(dis+1,dis+n+1,2147483647);dis[s]=0;q.push({dis[s],s});double ans=0;while(q.size()){int u=q.top().second;q.pop();if(vis[u])continue;vis[u]=true;ans+=dis[u];for(int i=u+u,j=2;i<=n;i+=u,j++){if(!vis[i]&&j<dis[i]){dis[i]=j;father[i]=u;q.push({dis[i],i});}} }return round(ans);
}
int main(){freopen("tree.in","r",stdin);freopen("tree.out","w",stdout);Read(n);Write(Prim(1));putchar(10);for(int i=1;i<=n;i++){if(father[i]){Write(father[i]);putchar(32);Write(i);putchar(10);}}fclose(stdin);fclose(stdout);return 0;
}

其实对比普通 Prim 算法 \(\mathcal O\left(n^2\right)\)，差别就两个：

使用小根堆 \(\mathcal O\left(\log_2 n\right)\) 求解离生成树最近的节点。
将 \(u\) 加入生成树后更新各节点 \(dis\) 值时，只更新满足 \(i\) 是 \(u\) 的倍数的节点 \(i\) 。

第一个很好理解，但第二个就有些理解困难了。

首先我们可以通过打表发现，\(f(i,j)=f(j,i)\)。

然后感性理解一通乱搞就得出了一个节点 \(i\) ，只有其父节点不为其约数时一定不优。

~~所以说这是一种感性理解的乱搞做法，但是却接近了正解思路。~~

\(100\text{pts}\)

通过打表，可以发现 \(f(i,j)=f(j,i)\)，严格数学证明如下：

若 \(i<j\)，则 \(f(i,j)=\dfrac{i\cdot f(j,i\bmod j)}{i\bmod j}=\dfrac{i\cdot f(j,i)}{i}=f(j,i)\)。

若 \(i=j\)，则 \(f(i,j)=f(j,i)\) 显然成立。

若 \(i>j\)，则 \(f(j,i)=\dfrac{j\cdot f(i,j\bmod i)}{j\bmod i}=\dfrac{j\cdot f(i,j)}{j}=f(i,j)\)。

那么，边 \((i,j)\) 的权值即 \(f(i,j)\)。

我们考虑如何使 \(\sum f(i,j)\) 尽可能地小。

延续刚才感性思考的思路，我们考虑证明找最大约数是最优的。

~~事实上我也是通过打表验证发现的。~~

对于边 \((i,j)\)，令 \(i>j\)，先讨论 \(i=kj\) 的情况，其中 \(k\) 为非负整数。

那么，\(f(i,j)=\dfrac ij=k\)。

此时 \(k\) 自然越小越好，即生成树上每一条边越小越好。

那么我们令 \(k\) 尽可能小，即令 \(j\) 尽可能大，即找最大约数。

但是，问题就在于，\(i=kj\) 不一定成立。

但是在生成树上，每一个 \(i\) 仅有一个父节点 \(f_i\)，那么我们找父节点 \(f_i=j\) 即可。

考虑快速找出 \(i\in[1,n]\) 的最大约数。

枚举最大约数

时间复杂度：\(\mathcal O\left(n^2\right)\)。

甚至不如直接求最小生成树......
质数筛法

要么埃式筛法 \(\mathcal O\left(n\log_2\log_2 n\right)\)，要么线性筛法 \(\mathcal O\left(n\right)\)。

筛出来以后就得到了每一个数的最小质因子，用该数除以最小质因子即可。
枚举最小约数

最坏时间复杂度 \(\mathcal O\left(n\sqrt n\right)\)，但是绝对跑不满。

\(i\) 从 \(1\sim n\) 枚举，\(j\) 枚举 \(1\sim\sqrt i\)，能跑满 \(\sqrt i\) 当且仅当 \(i\) 为质数。

否则会在之前就 break 跳出循环。

比如 \(2,4,6,8,10,12,\cdots\) 在 \(j=2\) 时就会跳出。

得到了 \(i\) 最小约数 \(j\) 后，\(\dfrac ij\) 即最大约数。

实测不会超时。

AC 代码

//#include<bits/stdc++.h>
#include<algorithm> 
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<ctime>
#include<deque>
#include<queue>
#include<stack>
#include<list>
using namespace std;
inline char gc(){static int p1,p2;static char buf[1<<20];if(p1==p2)p1=0,p2=fread(buf,1,1<<20,stdin);if(p1==p2)return EOF;return buf[p1++];
}
template<typename T>
inline void Read(T &x){x=0;char ch=gc();for(;ch<'0'||'9'<ch;ch=gc());for(;'0'<=ch&&ch<='9';ch=gc())x=(x<<3)+(x<<1)+(ch^48);
}
#define putchar putchar_unlocked
template<typename T>
inline void Write(T x){static char s[101];int top=0;do{s[++top]=x%10+'0';x/=10;}while(x);while(top)putchar(s[top--]);
}
const int N=3e6;
typedef long long ll;
int n,father[N+1];
int main(){freopen("tree.in","r",stdin);freopen("tree.out","w",stdout);Read(n);ll ans=0;//枚举最小约数for(int i=2;i<=n;i++){father[i]=1;ans+=i;for(int j=2;j*j<=i;j++){if(i%j==0){father[i]=i/j;ans+=j-i;break;}}}Write(ans);putchar(10);for(int i=1;i<=n;i++){if(father[i]){Write(father[i]);putchar(32);Write(i);putchar(10);}}fclose(stdin);fclose(stdout);return 0;
}